[Algorithm 04] Primary Number

※トップ画像はPixabayから引用しています

 素数検索

一般的な方法

import math

def is_primary(n):
   if n <= 1:
       return False
   for i in range(2, int(math.sqrt(n)) + 1):
       if n % i == 0:
           return False
       return True


val = input('Input Number: ')
for i in range(int(val)):
   if is_primary(i):
       print(i)

エラトステネスの篩

import math

def get_primary(n):
   if n <= 1:
       return []
   primary_list = [2]
   limit = int(math.sqrt(n))

   odd_list = [i + 1 for i in range(2, n, 2)]
   while limit > odd_list[0]:
       odd = odd_list[0]
       primary_list.append(odd)

       # 割り切れない奇数だけ残す
       odd_list = [i for i in odd_list if i % odd != 0]
   
   return primary_list + odd_list


val = input('Input Number: ')
print(get_primary(int(val)))