SHARE
TWEET

Untitled

a guest Oct 12th, 2017 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. def generate_primes(start, end):
  2.     primes = []
  3.     for i in range(start, end):
  4.         for j in range(2, i):
  5.             if i % j == 0:
  6.                 break
  7.         else:
  8.             primes.append(i)
  9.     return primes
  10.  
  11. def prime_factorization_with_help(x, primes, prime_factorization):
  12.     prime_factorization = prime_factorization or {}
  13.     for n in primes:
  14.         if not x % n:
  15.             prime_factorization[n] = prime_factorization.get(n, 0) + 1
  16.             prime_factorization_with_help(x/n, primes, prime_factorization)
  17.             break
  18.     return prime_factorization
  19.  
  20. def number_of_factors_with_help(prime_factorization):
  21.     answer = 1
  22.     for prime, power in prime_factorization.items():
  23.         answer *= power+1
  24.     return answer
  25.  
  26. def better_composite_count(limit):
  27.     answer = []
  28.     primes = generate_primes(2, limit//2)
  29.     most_divisors = 0
  30.     for x in range(limit):
  31.         _ = number_of_factors_with_help(prime_factorization_with_help(x+1, primes, []))
  32.         if _ > most_divisors:
  33.             most_divisors = _
  34.             answer.append(x+1)
  35.     return answer
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top