In principle, if the same algorithm is implemented in Python and C++ respectively, Python’s speed will certainly not match that of C++. However, Python is also known as a “glue language”; it allows us to write the main computational parts in efficient languages like C or C++, and then acts as a “binder” to join them together. Because of this, Python has a wide variety of extension libraries, many of which are written in C. Therefore, when writing Python programs, if we can use these existing libraries, the speed will be much faster. This article uses Numpy to improve the calculations from the previous post The Sum of Primes Below Two Million and the Sum of the First Two Million Primes.
The algorithm itself has not changed; only Numpy is used to handle array calculations. The code is as follows:
Sum of primes less than 2 million:
import time
import numpy as np
start=time.clock()
n=2000000
prime=np.arange(n+1,dtype=np.uint64)
r=int(np.sqrt(n))
for j in range(2,r+1):
if prime[j] != 0:
prime[j*j:n+1:j]=0
print(np.int64(prime.sum()-1))
end=time.clock()
print("time:",end-start)Sum of the first 2 million primes:
import time
import numpy as np
start=time.clock()
n=34000000
prime=np.arange(n+1,dtype=np.uint64)
r=int(np.sqrt(n))
for j in range(2,r+1):
if prime[j] != 0:
prime[j*j:n+1:j]=0
prime.sort()
z=np.where(prime==1)[0][0]
print(np.int64(prime[z+1:z+1+2000000].sum()))
end=time.clock()
print("time:",end-start)After these improvements, the computational efficiency has greatly increased, and the code is shorter. Testing on my computer (Win 8 + Python 3.4):
Sum of primes before two million:
142913828922
time: 0.13008331361399986Sum of the first two million primes:
31381137530481
time: 5.534884070836405
The speed is even faster than the previous code executed with PyPy!
About “Computer Disease”
On a side note, I feel like I’ve contracted “computer disease,” haha. Below is an introduction to “computer disease” from Surely You’re Joking, Mr. Feynman!:
As for Frankie, he had invented this “program,” and he had caught the disease that all computer people have: it’s a very serious disease and it interferes completely with the work. The trouble with computers is you “play” with them. They are so wonderful—all the buttons are under your control; you do this to get an even number, you do that to get an odd number. Before long, as long as you are smart enough, you can calculate more and more elaborate things.
But soon after, our system also broke down because Frankie couldn’t concentrate on his work, let alone supervise others. The computing system ran very, very slowly, while he sat in the room thinking about how to make the printer automatically calculate the arctangent of an angle. Well, the printer started moving, drawing lines one by one, making “whoosh! whoosh! whoosh!” sounds, calculating integrals while drawing, and then listing the arctangent values of all angles, all at once.
This was absolutely useless because we already had arctangent function tables. But if you’ve used a computer, you’ll fully understand this disease—the joy of discovering how capable you are. This was the first time he was infected with this symptom, and the funny thing is, that system was created by that poor fellow himself!
I really feel like I’ve caught this disease! ^_^
When reposting, please include the original address: https://kexue.fm/archives/2991
For more detailed information on reposting, please refer to: Scientific Space FAQ