[BEAKJOON] 백준 1978번 : 소수찾기

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

1978번: 소수 찾기

 

 

소수는 1과 자기 자신을 제외한 숫자 외에는 약수가 될 수 없다.

 

가장 기본적으로, 소수를 구하는 방법으로는, 해당 주어진 숫자를 2부터 본인숫자까지 나누어지지 않은다면 소수인데, 아니면 소수가 아닌 것이다. 그렇게 해당 주어진 숫자를 차례차례 계산하는 방법도 있기는 한데, 시간 복잡도가 높을 것이다.

2에서부터 자기 자신까지 모두 나눴을 때 나머지가 0이 되면 소수가 아니며, 0이 한번도 나오지 않는다면 소수이다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

 

구하려는 숫자가 커질 수록 시간이 그만큼 늘어나게 되므로 비효율적이다. 소수를 찾는데 가장 효율적인 알고리즘은 에라토스테네스의 체 이다.

 

에러 봉착

처음에 계속 런타임에러, 타입에러가 떠서 무엇이 문제이지?

했다.

소수 찾기에서 백준 1978 타입 에러가 뜰 이유가 있나 싶었지만, 리스트를 잘못 받아준 아주 기초적인 실수가 있었다.

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

이렇게 받았는데, 

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

위와 같이 바꾸어야 한다!

 

해결 코드

해당 문제에서 요구하는것은 소수의 갯수를 카운트 해주는 것이기 때문에, 나는 소수인 것은, 1로, 아닌 것은 0으로 설정해주었다.

그러면 해당 테이블 값에 접근해서 1이면 소수, 아니면 소수가 아닌것이다.

그래서 total count 값에 더하기만 하면 된다!

import sys
input = sys.stdin.readline

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

table = [1 for i in range(1001)]
table[1] = 0

for i in range(2, 501):
    if table[i] ==1:
        j = 2
        while i*j <= 1000:
            table[i*j] = 0
            j += 1

prime_count = 0

for i in range(0, n):
    prime_count += table[list[i]]

print(prime_count)