백준 boj 1978 - 소수 찾기 (파이썬, python)

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

1978번: 소수 찾기

 

너무 많은 시간 초과들과의 싸움이 있었고...

더는 시간초과로 골머리 썩고 싶지 않은 마음에

애초에 에라토스테네스의 체를 활용하여 문제를 풀었다.

 

문제에서 주어진 시간이 넉넉하여 이렇게 풀지는 않아도 될 것 같다.

 

문제는 최대 1000 까지의 숫자가 최대로,

미리 모든 수를 1로 채운 배열을 하나 생성하였다,

이후 모든 수의 배수는 0으로 바꿔, 소수가 아님을 표시했다.

 

이후 입력받은 수를 위 만들어 둔 배열에서 확인하는 식으로 풀이하였다.

 

code

max_val = 1000
dp = [1] * 1001

dp[0] = 0
dp[1] = 0 # 1은 소수가 아님
for i in range(2, max_val + 1):
    j = 2
    while i * j <= max_val:
        dp[i * j] = 0
        j += 1

n = int(input())
values = list(map(int, input().split()))
result = 0
for value in values:
    if dp[value]:
        result += 1
print(result)