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.
Recommended Posts