Primality test by Python

I implemented primality test of 100 or less using python in 3 ways. It also shows the time taken for each.

① Do not use built-in functions other than print (excluding time)


import time
n = 2

t1 = time.time()
while n <= 100:
    div = 0
    m = 1
    while m <= n:
        if n % m == 0:
            div += 1
        m += 1
    if div == 2:
        print(n)
    n += 1
time = time.time() - t1
print("time:{}".format(time))

Execution result

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 0.007971048355102539

② How to check one by one

import time

def ma(n):
    sosu_list = []
    t1 = time.time()
    for n in range(2,n + 1):
        div = 0
        for m in range(1,n + 1):
            if n % m == 0:
                div = div + 1
        if div == 2:
            sosu_list.append(n)
    print(sosu_list)
            
t1 = time.time()
ma(100)
time = time.time() - t1
print("time:{}".format(time))

Execution result [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] time:0.0027151107788085938

③ Eratosthenes sieve

import time

def eratosu(n):
        sosu_list = []
        false = []
        for i in range(2,n+1):
            if i not in false:
                sosu_list.append(i)
                for j in range(i*i,n+1,i):
                    false.append(j)
        return sosu_list
    
t1 = time.time()
print(eratosu(100))
time = time.time() - t1
print("time:{}".format(time))
            

Execution result [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] time:0.0005650520324707031

When comparing time, ① and ② basically did not change much. However, method (2) was not stable because the speed was sometimes close to that of (3). In comparison, the result was that the program (3) was the fastest of these. It's an algorithm called Eratosthenes sieving, but it's probably because it was very efficient and the amount of calculation was small (I've referred to the wiki, so I'll post a link).

Even for programs that output the same results, it is fun to try implementing them with different ideas, so I would like to continue.

Eratosthenes Sieve Wikipedia

Recommended Posts

Primality test by Python
Primality test with Python
Primality test with python
Algorithm in Python (primality test)
Python development helped by Jenkins-Unit test
Python Integrity Test
Visualization memo by Python
Communication processing by Python
Python basics 8 numpy test
Prime number enumeration and primality test in Python
Python test package memo
Beamformer response by python
python tag integration test
python unit test template
Speech recognition by Python MFCC
EXE Web API by Python
Newcomer training program by Python
Parameter setting by python configparser
Pin python managed by conda
Keyword extraction by MeCab (python)
Separate numbers by 3 digits (python)
Python template for Codeforces-manual test-
Markov switching model by Python
Image processing by python (Pillow)
Python started by C programmers
Python debug and test module
Platform (OS) determination by Python
Sort by date in python
Set python test in jenkins
[Python] Sort iterable by multiple conditions
Python
Competitive programming, coding test template: Python3
Expansion by argument of python dictionary
AtCoder: Python: Daddy the sample test.
Machine learning summary by Python beginners
Learn Python by drawing (turtle graphics)
test
Prime number generation program by Python
[Python] Test sample using unittest2, mock
Dickey fuller test by stats models
python sql statement extracted by time
Make Python dict accessible by Attribute
OS determination by Makefile using Python
Unit test log output with python
Typing automation notes by Python beginners
Write selenium test code in python
Efficient PCR test by pool method
Created AtCoder test tool for Python
Statistical test (multiple test) in Python: scikit_posthocs
Interval scheduling learning memo ~ by python ~
Behavior of python3 by Sakura's server
100 Language Processing Knock Chapter 1 by Python
Story of power approximation by Python
Blender 2.9, Python background light color test
Sorting files by Python naming convention
Explanation of production optimization model by Python
Get property information by scraping with python
Python> dictionary> values ()> Get All Values by Using values ()
[Python] What is inherited by multiple inheritance?
[Python] Super easy test with assert statement
Stress Test with Locust written in Python