백준 [브론즈2] 1978 소수 찾기

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

 

 

접근 방식

 

소수를 찾기 위해서는 먼저 해당하는 수의 약수를 모두 구해서 약수의 총합이 2개라면 소수라고 판결을 내린다 -> O(n)

그러나 위와 같은 방식은 실제 알고리즘 문제 풀이에서 사용하지 않는다!

 

N의 약수 쌍을 보면 둘중의 작은 값은 무조건 sqrt(N)의 범위 안에 존재한다

12 = > (1,12), (2,6), (3,4)

소수찾기는 모든 수를 보지 않고 sqrt(n) 만큼의 수만 확인해도 소수를 판별 할 수 있다

ex) 12라면 1,2,3,4,5,6,7,8,9,10,11,12 다 보는게 아니라, 1,2,3 까지만 봐도 소수 판별이 가능하다

 

즉 위와 같은 방식으로 O(n)이 아닌 O(sqrt(n)) 만큼의 시간 복잡도로 줄 일 수 있다

 

 

소스코드

 

 

N = int(input())
data = list(map(int, input().split()))
answer = 0

for number in data:
    sum = 0

    if number == 1 :
        continue

    for j in range(1,number+1):
        if j*j > number:
            break

        if number % j == 0:
            sum += 1

    if sum == 1:
        answer += 1

print(answer)

 

관련 자료

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