[WEEK01/DAY01] 백준 문제 : 소수 찾기

https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

 

오늘 풀었던 알고리즘 중에 제일 어려웠던 문제다.

 

소수는 약수가 1과 자기 자신밖에 없는 1보다 큰 자연수를 말한다.

그래서 1보다 큰 자연수 n이 주어졌을 때 n이 소수인지를 판별하는 가장 간단한 방법은

2에서 n-1 까지의 모든 자연수로 나누어 보는 것이다.

만약 한 경우에라도 나누어 떨어진다면, n은 소수가 아닌 것이다.

 

위 방법으로 풀이하면 시간 복잡도가 O(N)이 된다.

좀 더 빠른 방법이 있는데, 굳이 2에서 n-1까지 반복하지 않고 √n 까지만 반복해도 소수 여부를 판별할 수 있다.

자연수 12를 예로 들면, 12의 약수는 1, 2, 3, 4, 6, 12 인데 √12 (약 3.4641)를 기준으로 잘라서 양쪽을 보면 서로 대응되는 구조임을 알 수 있다.

3 * 4 = 12

2 * 6 = 12

1 * 12 = 12 인 것이다.

이 방법으로 풀이하면 시간 복잡도를 O(√N)까지 줄일 수 있다.

 

여기서 더 빠른 풀이방법이 있는데, 밀러-라빈 소수판별법(Miller-Rabin primality test)을 활용하는 것이다.

나는 수학에 참 약해서, 이를 아직 이해하지 못했으므로 설명은 위키피디아 링크로 대체한다.

https://ko.wikipedia.org/wiki/%EB%B0%80%EB%9F%AC-%EB%9D%BC%EB%B9%88_%EC%86%8C%EC%88%98%ED%8C%90%EB%B3%84%EB%B2%95

밀러-라빈 소수판별법 - 위키백과, 우리 모두의 백과사전

이 방법을 쓰면 시간복잡도를 O(klog^3N) 까지 줄일 수 있다고 한다.

어쨌든 나는 내가 구현할 수 있는 방법 중 가장 빠른 방법인, √n까지 반복하는 방법을 써서 구현했다.

 

아래 코드는 백준에 제출한 나의 답안이다.

 

import sys

n = int(sys.stdin.readline().strip())
numbers = sys.stdin.readline().split()

sum = 0

for i in range(n):
    check = True
    if int(numbers[i]) == 1 :
        check = False
    else :
        j = 2
        while j*j <= int(numbers[i]) and check == True:
            if int(numbers[i])%j == 0 :
                check = False
            j = j + 1

    if check == True:
        sum = sum + 1

print(sum)