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.

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.

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

Recommended Posts

Algorithm learned with Python 4th: Prime numbers
Algorithm learned with Python 10th: Binary search
Algorithm learned with Python 5th: Fibonacci sequence
Algorithm learned with Python 9th: Linear search
Algorithm learned with Python 7th: Year conversion
Algorithm learned with Python 8th: Evaluation of algorithm
Algorithm learned with Python 19th: Sorting (heapsort)
Algorithm learned with Python 6th: Leap year
Algorithm learned with Python 12th: Maze search
Algorithm learned with Python 11th: Tree structure
Algorithm learned with Python 13th: Tower of Hanoi
Algorithm learned with Python 16th: Sorting (insertion sort)
Algorithm learned with Python 14th: Tic-tac-toe (ox problem)
Algorithm learned with Python 15th: Sorting (selection sort)
Algorithm learned with Python 17th: Sorting (bubble sort)
Algorithm learned with Python 18th: Sorting (stack and queue)
Algorithm learned with Python 2nd: Vending machine
Algorithm learned with Python 3rd: Radix conversion
I tried it with SymPy Live, Wolfram Alpha and google with reference to "Algorithm learned with Python 4th: Prime numbers".
Prime numbers in Python
[Python3] Dijkstra's algorithm with 14 lines
Testing with random numbers in Python
Perceptron learning experiment learned with Python
Python data structures learned with chemoinformatics
Efficient net pick-up learned with Python
1. Statistics learned with Python 1-1. Basic statistics (Pandas)
Implementation of Dijkstra's algorithm with python
[Python] nCr mod Compute prime numbers
Python algorithm
I tried to create a list of prime numbers with python
[Python] Reactive Extensions learned with RxPY (3.0.1) [Rx]
Play handwritten numbers with python Part 2 (identify)
Search the maze with the python A * algorithm
1. Statistics learned with Python 1-3. Calculation of various statistics (statistics)
I searched for prime numbers in python
Let's develop an investment algorithm with Python 1
FizzBuzz with Python3
Scraping with Python
Statistics with python
Generate two correlated pseudo-random numbers (with Python sample)
Python memorandum (algorithm)
Scraping with Python
Python with Go
Solve with Ruby and Python AtCoder ABC084 D Cumulative sum of prime numbers
Twilio with Python
Integrate with Python
Play with 2016-Python
AES256 with python
Tested with Python
1. Statistics learned with Python 1-2. Calculation of various statistics (Numpy)
Find prime numbers in Python as short as possible
python starts with ()
Note for formatting numbers with python format function
with syntax (Python)
Bingo with python
Zundokokiyoshi with python
Use Python and word2vec (learned) with Azure Databricks
1. Statistics learned with Python 2-1. Probability distribution [discrete variable]
Find the shortest path with the Python Dijkstra's algorithm
Generate n correlated pseudo-random numbers (with Python sample)
Solving the Python knapsack problem with the greedy algorithm