diff options
| -rw-r--r-- | src/projecteuler/058.py | 39 |
1 files changed, 39 insertions, 0 deletions
diff --git a/src/projecteuler/058.py b/src/projecteuler/058.py new file mode 100644 index 0000000..a483fac --- /dev/null +++ b/src/projecteuler/058.py @@ -0,0 +1,39 @@ +from common import sieve + +primes = sieve(30000).primes() +prime_list = list(primes) +prime_list.sort() + +def is_prime(n): + if n in primes: + return True + for p in prime_list: + if p*p > n: + return True + if n % p == 0: + return False + return True + +def count_primes(numbers): + prime = 0 + for n in numbers: + if is_prime(n): + prime += 1 + return prime + +#numbers = [1, 3, 5, 7, 9] +prime_count = 3 +number_count = 5 +level = 2 +last = 9 + +while 10*prime_count >= number_count: + step = 2 * level + numbers = [last+step, last+2*step, last+3*step, last+4*step] + prime_count += count_primes(numbers) + number_count += 4 + level += 1 + last += 4*step + +print 2*(level-1) + 1 + |