👐 Primality Test

※ 소수(Prime Number) = 1과 자기 자신으로만 나누어지는 수 ※

1. 약수의 개수

👐

① 2~(N-1) 까지 모두 돌렸을 때 나머지가 0이 아니다

 

② 약수의 개수가 2

def isPrime1(N):
    for i in range(2,N):
        if N%i == 0:
            return False
    return True

def isPrime2(N):
    cnt = 0
    for i in range(1,N+1):
        if N%i == 0:
            cnt += 1   
    if cnt == 2:
        return True
    else:
        return False

→ 위 두 풀이는 모두 O(N) 모든 범위를 돌며 일일이 확인

2. O(N^(1/2))

👐

③ 탐색 범위 N^(1/2)으로 줄이기

→ 위와 동일하되 시간복잡도 O(N^(1/2)). 나누어지는 지 알아보는 수는 N의 제곱근 범위 내에서만 판별하면 충분하다.

증명) N이 어떤 두 수로 나누어진다고 하면 N=p*q. p / q 둘 중 하나는 반드시 N의 제곱근 이하이기 때문에, 제곱근 내의 범위만 판정 충분

#N//2
def isPrime3(N):

    for i in range(2,int(N//2)+1):
        if N%i == 0:
            return False
    
    return True

#root(N)
def isPrime4(N):

    for i in range(2,int(N**(1/2))+1):
        if N%i == 0:
            return False
    
    return True

3. Sieve of Eratosthenes

→ 1부터 N까지의 자연수 중 소수를 구한다면

 

순서 ①. 2부터 N까지 모든 자연수를 나열한다.

순서 ②. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.

순서 ③. 남은 수 중에서 i의 배수를 모두 제거한다. (i는 제거하지 않는다)

순서 ④. 더 이상 반복할 수 없을 때까지 ②와 ③을 반복한다. (탐색범위 N^(1/2))

 

ex) 1부터 1000까지의 모든 자연수 중 소수만 출력하기

#1~1000 Primality Test
sieve = [True]*1001
sieve[0],sieve[1] = False,False

for i in range(2,int(1000**(1/2))+1):
    if sieve[i] == True:
        for j in range(i,1001,i):
            sieve[j] = False
        sieve[i] = True

ans = [i for i in range(2,1001) if sieve[i] == True]
print(ans)

 

→ 파이썬 코드 설명 

 

* ①) N+1개의 True가 들어간 sieve 초기화 / sieve[0]과 sieve[1] False 설정(2부터 iterate)

 

* ②) 2부터 N^(1/2)까지의 범위 for문 돌리고 / 해당 수 i가 아직 판정 가능한 True라면 (if sieve[i] == True)

 

* ③) for문 내의 for문으로 j가 i부터 N까지 i의 step으로 돌며, 즉 i의 배수만큼 돌며 모두 False 처리 / 나 자신 i는 다시 True 처리 (sieve[i] = True)

 

→ O(NloglogN)의 시간복잡도. 일반적으로 100만(1,000,000)까지 소수 판별 가능. 다만, 각 자연수의 소수 여부를 저장해야 하므로 메모리 많이 필요. 예를 들어 10억이 소수인지 아닌지 알려면 10억개만큼의 메모리 공간이 필요.

4. 소수 기타 성질

① 소수는 2와 3, 그리고 6으로 나눈 나머지 1 또는 5

→ 모든 자연수는 6k, 6k+1, 6k+2, 6k+3, 6k+4, 6k+5로 나타낼 수 있고, 여기서 6k+1, 6k+5 제외 다른 형태는 2 또는 3으로 나누어지는 것을 확인할 수 있으므로, 만약 소수가 존재한다면, 그리고 2와 3이 아니라면 무조건 6으로 나눈 나머지 1또는 6일 것이라는 걸 예상할 수 있다. 이를 소수 판별 알고리즘에 적용하면 전체 N의 범위 탐색을 N/3으로 줄일 수 있게 된다.

 

② 베르트랑 공준(베르트랑-체비쇼프 정리; 베르트랑 가설)

→ 임의의 자연수 n>=2에 대하여, n<p<=2n인 소수 p가 항상 존재.

(BOJ 4948 베르트랑 공준)

 

③ 골드바흐의 추측 / 골드바흐 파티션

 

→ 골드바흐의 추측) 2보다 큰 짝수는 모두 두 소수의 합으로 나타낼 수 있다.

(BOJ 9020 골드바흐의 추측)

 

→ 골드바흐 파티션) 2보다 큰 짝수를 두 소수의 합으로 나타내는 표현

(BOJ 17103 골드바흐 파티션)