Implement the basic algorithm in Python to deepen your understanding of the algorithm. As the fourth bullet, we will deal with prime numbers. Not only primality test, but also implementation of an algorithm called Eratosthenes sieve.
There are innumerable numbers, but it is known that it is sufficient to search up to the square root of the number when determining a prime number. In the following, we show a program that finds prime numbers by three methods, but we also show and consider the code for evaluating them.
First, implement a program that outputs prime numbers up to a certain number based on the principle. The code is shown below.
prime1.py
"""
2020/12/16
@Yuya Shimizu
Find a prime number
"""
import math
#Primality test function
def is_prime(n):
if n <= 1:
return False
for i in range(2, int(math.sqrt(n)) + 1): #Repeatedly search up to the square root range
if n % i == 0:
return False
return True
prime = []
for i in range(100):
if is_prime(i):
prime.append(i)
print(prime)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
By giving 100 as an argument of the function, we were able to obtain prime numbers up to 100. Finally, the evaluation is performed by comparing with the other two methods.
It is known as a method for efficiently finding prime numbers. Specifically, a number divisible by 2 (a multiple of 2), a number divisible by 2 (a multiple of 3) ,. .. .. The idea is that only prime numbers remain at the end, excluding them in order. The code implemented is shown below.
eratosthenes.py
"""
2020/12/16
@Yuya Shimizu
Find a prime number
Eratosthenes Sieve
"""
import math
def get_prime(n):
if n <= 1:
return []
prime = [2]
limit = int(math.sqrt(n))
#Odd list generation
data = [i + 1 for i in range(2, n, 2)]
while limit > data[0]:
prime.append(data[0])
data = [j for j in data if j % data[0] != 0]
return prime + data
print(get_prime(100))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
The same result as before was obtained. The third method uses the functions already prepared.
Sympy has a primality test function `isprime ()`
and a desired function `sieve.primerange ()`
.
Since this is a function already prepared, it is very easy to implement. After implementation, it is evaluated by comparing with the other two methods.
prime2.py
"""
2020/12/16
@Yuya Shimizu
Find a prime number
"""
from sympy import sieve
print([i for i in sieve.primerange(1,100)])
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
With just this program, we got the same results as the other methods. Finally, we evaluate these three programs based on the execution time.
Each implementation program is shown below.
prime1_evaluation.py
"""
2020/12/16
@Yuya Shimizu
Find a prime number
"""
import math
import time
def is_prime(n):
if n <= 1:
return False
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
return True
#Evaluation of execution time
start = time.time()
prime = []
for i in range(100000):
if is_prime(i):
prime.append(i)
print(prime)
process_time = time.time() - start
print(process_time)
eratosthenes_evaluation.py
"""
2020/12/16
@Yuya Shimizu
Find a prime number
Eratosthenes Sieve
"""
import math
import time
def get_prime(n):
if n <= 1:
return []
prime = [2]
limit = int(math.sqrt(n))
#Odd list generation
data = [i + 1 for i in range(2, n, 2)]
while limit > data[0]:
prime.append(data[0])
data = [j for j in data if j % data[0] != 0]
return prime + data
start1 = time.time()
print(get_prime(100000))
process_time1 = time.time() - start1
print(process_time1)
prime2_evaluation.py
"""
2020/12/16
@Yuya Shimizu
Find a prime number
"""
from sympy import sieve
import time
start = time.time()
print([i for i in sieve.primerange(1,100000)])
process_time = time.time() - start
print(process_time)
This time, each program calculated prime numbers up to 100 and prime numbers up to 1000000, and measured the time. The results are summarized below.
Prime number | Program 1(principle) | Program 2(Eratosthenes Sieve) | Program 3(sympy function) |
---|---|---|---|
Up to 100[s] | 0.00 | 0.01 | 0.02 |
Up to 1000000[s] | 8.78 | 5.87 | 4.71 |
For prime numbers up to 100, there is not much difference because the processing is short, but the wider the search range for prime numbers, the greater the difference in processing time. Especially for program 1, it is slower than the other two methods. In other words, it can be said that the other two methods are able to efficiently search for prime numbers. Furthermore, program 3 is one second faster than the program based on the Eratosthenes sieve for efficiently finding prime numbers. Program 3 uses sympy functions, and the results show that the program is simple and the processing time can be shortened considerably.
I was surprised that Program 3 was the fastest. I expected that the Eratosthenes sieve program would be the fastest, but the sympy function was excellent. Since the program is simple, I thought that I should use the sympy function when finding the prime number. However, since I don't know the contents of sympy, I may not be able to say it easily. In addition, the usefulness of the algorithm was once again felt by comparing it with Program 1 based on the principle. Such a feeling further enhances the morale to learn the algorithm.
Introduction to algorithms starting with Python: Standards and computational complexity learned with traditional algorithms Written by Toshikatsu Masui, Shoeisha
Recommended Posts