Advertisement
danchaofan

Euler #214

Dec 26th, 2017
146
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.93 KB | None | 0 0
  1. def factorize(n):
  2.     factors = []
  3.     while n % 2 == 0:
  4.         factors.append(2)
  5.         n = int(n / 2)
  6.     for b in range(3, int(n ** 0.5) + 1, 2):
  7.         while n % b == 0:
  8.             n = int(n / b)
  9.             factors.append(b)
  10.     if n > 2:
  11.         factors.append(int(n))
  12.     return set(factors)
  13.  
  14.  
  15. def totient(n):
  16.     coprimes = n
  17.     for x in factorize(n):
  18.         coprimes *= (1 - (1 / x))
  19.     return int(coprimes)
  20.  
  21.  
  22. def primes_sieve(limit):
  23.     a = [True] * limit
  24.     a[0] = a[1] = False
  25.  
  26.     for (i, isprime) in enumerate(a):
  27.         if isprime:
  28.             yield i
  29.             for n in range(i * i, limit, i):
  30.                 a[n] = False
  31.  
  32. answer = 0
  33. for b in list(primes_sieve(40*10**6)):
  34.     print(b)
  35.     original = b
  36.     for c in range(24):
  37.         b = totient(b)
  38.         if (b == 1) and (c != 23):
  39.             break
  40.         if (b == 1) and (c == 23):
  41.             answer += original
  42. print(answer)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement