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