소수 판별에 대한 고찰

소수 판별은 기초적인 알고리즘이며 여전히 코딩 테스트에서도 자주 출몰하고 여러 문제에 섞여들어가고는 하는 단골 유형이다. 그렇다면 소수를 판별하는 방법에 대해 고민해보자.

 

단일 소수 판별법

하나에 자연수에 대해 소수인지 판별하는 경우

 

아래와 같은 시간복잡도로 해결할 수 있다.

 

1. O(N) - 모두 탐색

 

말 그대로 모두 탐색하면 된다.

n=(int(input())

isPrime=True if n>1 else False

for i in range(2,n):
    if n%i==0:
        isPrime=False
        break

위와 같이 코드를 작성하면 2~n-1 까지의 수로 모두 나눠보며 나눠진다면 최종적으로 isPrime은 False일 것이고 나눠지지 않는다면 최종적으로 isPrime은 True일 것이다.

 

하지만 이렇게 하면 1초 동안 1억 이내의 숫자만 소수인지 판별할 수 있을 것이다. 굳이 2~(n-1)까지의 수로 나눠보아야 할까?

2. O(N) 조금 더 빠르게

 

생각을 조금 더 해보면 굳이 n-1까지 탐색해볼 필요는 없다. n/2까지만 탐색해도 충분하다. 그 이유는 간단하다. 가장 작은 소수가 2이다. 즉 n/2보다 큰 수로 나누어서 나누어 떨어질 가능성이 아예 없다는 얘기이다.

 

n=(int(input())

isPrime=True if n>1 else False

for i in range(2,n//2):
    if n%i==0:
        isPrime=False
        break

 

조금 더 빨라졌다. 2억 이내의 소수는 1초 정도면 구할 수 있다. 하지만 유의미할 정도의 차이는 아니다.

여기서 속도를 더 높일 수 있는 방법은 없을까?

 

3. O(N^0.5)

 

사실 루트 n까지의 숫자만 나눠보아도 된다.

증명은 아래와 같다.

X라는 수가 합성수라면 X=M*N (M>=N) 으로 나타낼 수 있다. M>=N이므로 M*M>=M*N 이고 즉 M*M>=X 이다.

M>=루트 X 이고 이 M의 최소값이 즉 루트 X이고 2~M 사이의 값 중에서는 N이 들어있으므로 N의 최댓값은 M의 최솟값인 루트 X가 된다. 즉 N까지의 수, 루트 X까지의 값만 탐색해보면 소수인지 판별할 수 있다.

위 증명에 따라서 우리는 루트 N까지만의 수들로 소수인지 판별할 수 있다.

 

n=(int(input())

isPrime=True if n>1 else False

for i in range(2,int(n**0.5)+1):
    if n%i==0:
        isPrime=False
        break

단일 자연수 하나에 대해 10**16의 수까지 1초 정도에 소수인지 판별할 수 있다.

코딩 테스트나 대회에서 나오는 문제들도 대부분 저 범위 밖의 소수 판별 문제를 내지는 않고 사실상 단일 소수 판별에 대한 코딩 테스트에 나올 수 있는 가장 빠른 방법으로 알고 있어도 무리는 없다고 생각한다. 

 

이 밖에 좀 알려진 소수 판별법으로는 O(klog^2N)의 시간복잡도를 갖는 밀러 - 라빈 소수판별법도 있기는 한데 매우 높은 확률이긴 한데 확률적인 알고리즘이기도 하고, 코딩 테스트에서는 나올 일도 없고, 대회 준비용으로도 그렇게 유용한 알고리즘은 아니라고 생각한다.

 

~N 까지의 수들에 대해 소수 판별

 

여러 수가 소수인지 판별하고 정보를 저장하기 위해서 배열을 이용해서 구현하고는 한다.

 

n=(int(input())

isPrime=[True]*(n+1)
isPrime[0]=isPrime[1]=False

for i in range(2,n+1):
    if isPrime[i]==False:
        continue
    for j in range(i+i,n+1,i):
        isPrime[j]=False

 

나는 일반적으로 위와 같은 형태로 구현하고는 한다. 다만 위에서 사용한 테크닉을 이용한다면 굳이 j+1까지 탐색할 필요가 없다는 것을 알 것이다.

 

n=(int(input())

isPrime=[True]*(n+1)
isPrime[0]=isPrime[1]=False

for i in range(2,int((n+1)**0.5)+1):
    if isPrime[i]==False:
        continue
    for j in range(i+i,n+1,i):
        isPrime[j]=False

 

이러한 것을 "에라토스테네스의 채"라고 하며 시간복잡도는 O(Nlog(log(N)))이다.

 

 

결론

 

결론적 2가지만 알면 된다. 단일 소수에 대해 O(루트 N)으로 판별하기랑 에라토스테네스의 채 이 두가지만 알 고 있어도 코딩 테스트는 물론이고 대회까지 어지간해서는 걱정 없다고 생각한다.