Advertisement
Guest User

Untitled

a guest
Oct 12th, 2017
186
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.09 KB | None | 0 0
  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
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement