[BAEKJOON] 1978번: 소수 찾기

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

 

코드

1. 반복문 돌면서 소수 여부 판별

import sys, math

input = sys.stdin.readline

n = int(input())
num = list(map(int, input().split()))
# 소수 카운트 하기
cnt = 0
for i in num:
	# 0과 1은 소수가 아니니까 continue
    if i == 0 or i == 1:
        continue
    # 소수는 1과 자기 자신만 약수로 가지는 수 
    for j in range(2, int(i**0.5)+1):
        if i % j == 0:
        	# 1과 자기 자신말고 나누어 지는 수 == 약수 아님
            break
    else:
        cnt += 1

print(cnt)

 

약수는 대칭을 이루기 때문에, 약수를 판별할 때 제곱근을 이용하면 연산을 더욱 줄일 수 있다.

 

2. 에라토스테네스의 체 알고리즘을 사용해서 소수 찾기

import sys

input = sys.stdin.readline

n = int(input())
num = list(map(int, input().split()))

max_ = 1_000
check = [0] * (max_ + 1)
# check[]가 True면 소수가 아님
check[0], check[1] = True, True

# 에라토스테네스의 체 알고리즘
for i in range(2, max_+1):
    j = i+i
    while j <= max_:
        check[j] = True
        j += i

print(sum(1 for i in num if not check[i]))

에라토스테네스의 체를 사용해서 소수 찾기

1. 2부터 소수 찾기 (1은 소수가 아니다.)

2. 찾은 소수의 배수는 모두 제거 ( ex) 2의 배수 모두 제거 )

3. 다음으로 남아있는 가장 작은 수 찾기 (그 수가 소수)

4. 찾은 소수의 배수를 모두 제거

5. 위 과정을 반복한다.

위의 코드에서는 max_가 1000이므로 1부터 1000까지의 수 중에 소수를 찾는 코드이다.

 

나의 생각

작은 입력 데이터에서는 두 코드 간의 차이가 크지 않을 수 있으며, 큰 입력 데이터에서는 두 번째 코드가 미리 소수 목록을 구해 놓는 이점 때문에 더 효율적이다.