Algorithm learned with Python 4th: Prime numbers

#Algorithms learned in Python

Introduction

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.

Primality test

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.

Primality test

First, implement a program that outputs prime numbers up to a certain number based on the principle. The code is shown below.

code

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)

output

[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.

Primality test: Eratosthenes sieve

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.

code

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))

output

[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.

Find prime numbers: using sympy

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.

code

prime2.py

"""
2020/12/16
@Yuya Shimizu

Find a prime number
"""
from sympy import sieve

print([i for i in sieve.primerange(1,100)])

output

[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.

Evaluation test

Each implementation program is shown below.

Code 1

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)

Code 2

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)

Code 3

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)

result

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.

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.

Impressions

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.

References

Introduction to algorithms starting with Python: Standards and computational complexity learned with traditional algorithms Written by Toshikatsu Masui, Shoeisha