# 소수 알고리즘 -1

def primeNumber(n):
    for i in range(2, n):
        if n % i == 0:
            return False #소수x
    return True # 소수

이 알고리즘은 제일 기본적인 알고리즘으로 시간복잡도로 O(n)을 가진다.

소수 알고리즘 - 2

def primeNumber(x):
   for i in range(2,int(math.sqrt(x))+1):
       if x % i ==0:
           return False 
   return True #소수당 

약수의 성질을 활용해 제곱근만 검사하는 방법이다

그렇기에 시간복잡도는 O(N^1/2)를 가진다

에라토스테네스의 체

n = 1000
a = [False,False]+[True]*(n-1)
primes = [] #소수배열 

for i in range(2,n+1):
    if a[i]:
        primes.append(i)
        for j in range(2*i,n+1,i): #2+i부터 n+1까지 i간격 
            a[j] = False 
print(primes)

0과 1는 소수가 아니므로 a에 false를 저장해두고 나머지에 True를 저장해두고 하나씩 프라임에 넣고 그의 배수들은 False르 변경시켜서 탈락시키는 방법이다 !

시간 복잡도는 O(Nlog(logN))로 가장빠르다!!