The title mentions two rather interesting programming problems. If the reader finds the title dizzyingly confusing, let me state it more clearly:
Sum of primes below two million refers to the sum of all primes not exceeding two million;
Sum of the first two million primes refers to the sum of the first two million prime numbers.
I saw these problems on Zimou’s blog. The former is Project Euler Problem 10, and the latter is something Zimou and I explored for fun. For Zimou’s research and code, you can visit his blog to learn more. In this article, I will share my own thoughts.
Both problems are essentially about the construction of prime tables. The first is slightly simpler, while the second is a bit more complex and involves a larger amount of computation. Both constructing a prime table and testing for primality use the basic "Sieve of Eratosthenes," which involves dividing n by primes from 2 to \sqrt{n}. For programming convenience, we usually divide by all integers from 2 to \sqrt{n}. However, since the numbers involved in these problems are very large, improving efficiency is highly necessary. Therefore, we must implement a method that only divides n by primes from 2 to \sqrt{n}.
It is important to note that many readers have a misunderstanding of the sieve method. Generally, one might use the method of dividing n by primes from 2 to \sqrt{n} to determine the primality of n, then iterate through numbers from 1 to 2 million, and finally sum all the primes. While this is feasible, the efficiency is significantly compromised! One should know that the original Sieve of Eratosthenes does not work by division; it is described as follows:
Sieve of Eratosthenes
To find all primes not exceeding n, first find all primes 2, 3, 5, \dots, p_m from 2 to \sqrt{n}. Then, sequentially delete multiples of 2 (except 2 itself), multiples of 3 (except 3 itself), ..., and multiples of p_m (except p_m itself) from the range 1 to n.
In other words, constructing a prime table using the Sieve of Eratosthenes only requires multiplication and deletion operations! Multiplication is much more efficient than division, and such an algorithm requires far fewer operations than checking each number individually.
The idea for implementing the above algorithm in programming is to first construct an array containing all integers from 1 to n, and then sequentially set the terms that are multiples of 2 to 0, multiples of 3 to 0, ..., and multiples of p_m to 0. But how do we get the primes from 1 to \sqrt{n}? It is actually simple: just take them from the array as you go—that is, collect them while checking. The speed of prime generation is faster than the rate at which the required number of primes increases. (This means, for example, within the range of 20, you only need to delete the multiples of 2 and 3 to get all primes 2, 3, 5, 7, ..., 19. The largest prime reached is 19, which is sufficient for determining primes up to 19^2 = 361. To get each prime p_i from 2 to \sqrt{n}, we just take the non-zero terms from the front of the array, because composite numbers have already been set to 0. With a little thought, the reader will find that this process advances step-by-step.)
At this point, the basic logic for programming has emerged. However, we also need to consider that these two problems involve large-number arithmetic, especially the second one, where the first two million primes mean primes up to approximately 35 million. At this stage, we must consider the choice of programming tools. I initially thought of using C++, as it is highly efficient, but C++ has limits on array sizes and integer types, making it prone to overflow. I then considered using the GMP large-number library with C++, but my foundation in C++ was too weak to set it up properly (it is said that the author of GMP refuses to support VC and VS, and the methods found online are community-modified. I also thought about writing a simple large-number class myself but didn’t have the heart to tinker with it). I also considered Matlab, but Matlab does not support high-precision large-number arithmetic and produces approximate values, which is unsuitable. I even thought of Mathematica, which is a symbolic computation tool that supports operations on ultra-large integers, but I found that Mathematica is very slow when processing arrays with millions of elements. Finally, I settled on Python.
I had tried Python a long time ago but set it aside for a very long time. Today, I discovered that Python natively supports large-integer arithmetic! Although its efficiency cannot match C++, it can easily complete the programming tasks in this article, and with optimization, the time taken has been greatly reduced. I have attached the code below to share with everyone.
Test Results:
In Python 3.3:
Sum of primes below two million:
142913828922
time: 2.4048174478605646Sum of the first two million primes:
31381137530481
time: 46.75734807838953
It is said that using Python 2.7 would be faster, but in my actual tests on my machine, there was no significant difference. The average time to calculate the sum of the first two million primes is around 50 seconds, which is faster than Zimou’s algorithm. The reason should be that I used a constructive method rather than checking each number individually to obtain the prime table. Similarly, both Zimou and I only used primes between 2 and \sqrt{n} for checking, rather than all integers.
Looking forward to seeing even more efficient algorithms in Python!
Sum of primes within 2 million
# Sum of primes within 2 million
import time
start = time.clock()
import math
n = 2000000 # Define upper limit
prime = [i for i in range(1, n + 1)] # Define integer list
r = int(math.sqrt(n))
# Below is the deletion method to remove composite numbers from the list
for j in range(2, r + 1):
if prime[j-1] != 0:
s = j * j
while s <= n:
prime[s-1] = 0
s = s + j
print(sum(prime) - 1) # Summation
end = time.clock()
print("time:", end - start)Sum of the first 2 million primes
# Sum of the first 2 million primes
import time
start = time.clock()
import math
n = 35000000
# Define upper limit; 2 million primes are approximately within the first 35 million integers.
# This is based on the prime-counting function approximation pi(n) approx n/ln(n).
prime = [i for i in range(1, n + 1)] # Define integer list
r = int(math.sqrt(n))
# Below is the deletion method to remove composite numbers from the list
for j in range(2, r + 1):
if prime[j-1] != 0:
s = j * j
while s <= n:
prime[s-1] = 0
s = s + j
# Start determining the count of primes up to 2 million.
prime.sort() # Sort in ascending order (placing 0s at the beginning)
z = prime.count(0) # Count the number of 0s
print(sum(prime[z+1:z+1+2000000])) # Calculate the sum of the first 2 million primes.
end = time.clock()
print("time:", end - start)When reposting, please include the original address: https://kexue.fm/archives/2612
For more detailed reposting matters, please refer to: Scientific Space FAQ