Many problems in Project Euler relate to working with primes. I use primesieve-python to help solve such problems. It consists of Python bindings for the primesieve C++ library. Generates primes orders of magnitude faster than any pure Python code. Features:
- Generate a list of primes
- Count primes and prime k-tuplets
- Print primes and prime k-tuplets
- Find the nth prime
- Iterate over primes using little memory
Anyway, here’s Problem 50 from Project Euler:
Here’s how I did it:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # Question: Which prime, below one-million, can be written as the sum of the most consecutive primes | |
| from primesieve import * | |
| from math import * | |
| # Generate list of primes under a million | |
| primes_under_million = generate_primes(10**6) | |
| # Sum of consecutive primes is of order 0.5(n^2)(logn) | |
| # Calculate 'n' so that sum of consecutive primes is less than a million (and not necessarily prime) | |
| nsum = 1 | |
| n = 1 | |
| while nsum < 10**6: | |
| nsum = 0.5*(n**2)*(log(n, e)) | |
| n += 1 | |
| # Calculate index so that sum of first 'index' consecutive primes is under a million and also prime | |
| primes_subset = primes_under_million[:n] | |
| nsum = sum(primes_under_million[:n]) | |
| while nsum > 10**6: | |
| n -= 1 | |
| nsum = sum(primes_under_million[:n]) | |
| primes_sum = 0 | |
| index = 0 | |
| for i in range(len(primes_subset)): | |
| if i % 2 == 1: | |
| pass | |
| else: | |
| sumprimes = sum(primes_subset[:i]) | |
| if sumprimes > primes_sum and sumprimes < 10**6 and sumprimes in primes_under_million: | |
| primes_sum = sumprimes | |
| index = i | |
| # Print out sum of consecutive primes till 'index', index, n | |
| # print primes_sum, index, n | |
| # Check consecutive primes within a range (index to n) such that their number is greater than index and maximum | |
| j = index + 1 | |
| start = 0 | |
| while j <= n: | |
| while (j-start) >= (n-index): | |
| sumprimes = sum(primes_subset[start:j]) | |
| if sumprimes > primes_sum and sumprimes in primes_under_million: | |
| primes_sum = sumprimes | |
| start += 1 | |
| j += 1 | |
| start = 0 | |
| print primes_sum | |
Answer: 997651
Discovering Python & R 