[TIL][W1/Sun] 소수찾기

🧾 1과 자신 이외의 자연수로는 나눌 수 없는 자연수 1은 소수가 아니다.

소수의 성질을 이용하여 소수를 판별한다.

소수 판별 문제 유형

소수 판별이 필요한 문제 유형은 크게 두가지로 보인다.

1. 소수를 반별
2. 특정 범위 내에서 소수를 찾아 반환하기

소수 판별 (True/False)

N을 이용하기

2부터 n-1까지 나누기

def isPrimeNum(n):
    for i in range(2,n): #2~n-1까지의 모든 수를 나누어 확인
        if n%i==0:
            return False
        return True

시간복잡도 : O(n)

n이 1,000,000(백만)일 때 2~999,999의 모든 수를 하나씩 나누기 때문에 비효율적이다.

n/2 까지 나누기

def isPrimeNum(n):
		ref=int(n/2)+1
    for i in range(2,ref): #2~n/2까지의 모든 수를 나누어 확인
        if n%i==0:
            return False
        return True

자기자신의 반절 까지의 수로 나누었을 때 나누어떨어진다면 그건 소수가 아니다. 마찬가지로 시간복잡도가 O(n)이므로 크게 차이나지 않는다.

n의 제곱근까지 나누기

소수가 아닌 수의 성질을 이용하여 범위를 좁히는 방법. 약수가 있는 수들을 생각해본다면..

#25
1*25=25
5*5=25
1 5 25

#36
1*36
2*18
3*12
4*9
6*6
1 2 3 4 6 8 12 18 36

#18
1*18
2*9
3*6
1 2 3 6 9 18

정확히 대칭을 이룬다. 제곱근이 자연수일 경우가 아니더라도 말이다. 따라서 어떤 자연수의 제곱근(혹은 그에 가까운 자연수)까지의 범위 내에서의 수를 가져와 테스트를 돌린다면 소수인지 아닌지 판별 가능하다.

import math
def isPrimeNum(n):
    ref=int(math.sqrt(n))+1 #제곱근까지의 범위를 구해야 하므로 +1
    for i in range(2,ref): #2~제곱근
        if n%i==0:
            return False
        return True

시간복잡도는 O(√N)로 훨씬 낫다.

범위 내 소수 구하기(list)

다수의 소수 판별로, N보다 작거나 같은 모든 소수를 찾을 때 사용한다.

에라토스테네스의 체

1. 2부터 N까지의 모든 자연수를 나열한다.
2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
3. 남은 수 중에서 i의 배수를 모두 제거한다.(i는 제거하지 않는다.)
4. 더 이상 반복 불가능할때까지 2와 3을 반복.

import math

def isPrimeNum(n):
    #n=17
    arr=[True for i in range(n+1)] #모든 수가 소수라고 가정 #index 임을 고려 n+1
    ref=int(math.sqrt(n))+1  #1~제곱근까지의 모든 수를 확인
    
    #에라토스테네스의 체 알고리즘
    for i in range(2,ref):
        #배열의 index에서 i를 제외한 모든 i의 배수를 지운다.
        if arr[i]: #i가 소수인 경우(아직 지워지지 않은 수일 때)
            j=2    #2부터 시작(1은 소수가 아님)
            while i*j<=n: #i*j는 배수를 뜻한다.
                arr[i*j]=False #배수가 되는 index의 값을 모두 false로 바꾼다
                j+=1     
    for i in range(2,n+1): 
        if arr[i]:
            print(i, end=' ')

isPrimeNum(17)

코드 구현 point

• 소수를 판별한다고 수를 배열에 넣는 것 대신 배열 내에는 T/F을 사용
• 인덱스의 숫자로 소수를 판별
• 모든 수가 소수라고 가정하는 배열 작성은 모든 인덱스에 True를 넣는다.
• j를 따로 설정하여 i*j로 배수가 되는 index들을 전부 False로 변환
• 결과적으로 최종 출력 시에는 배열 값이 True인 index 의 숫자만 반환하면 그것이 소수

장점과 단점

시간복잡도가 O(NloglogN) 으로 매우 빠르나, 각 자연수에 대한 소수 여부를 판별하여 배열을 미리 선선해두므로 메모리가 많이 필요하다.

관련 문제

차후 링크 걸기

• 백준 소수찾기
• 백준 골드바흐의 파티션 (중)

 

관련 생각할 요소 

백준의 답변인데 시간복잡도 등에 대한 코멘트를 다시 한번 보기 위해 메모해둠.

https://www.acmicpc.net/board/view/82413