[백준 1978번] [Python] 소수 찾기

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

1978번: 소수 찾기

 

난이도 : 실버 5
태그 : 정수론, 수학, 소수판정

 

 

설명

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

1978번: 소수 찾기

 

주어진 n개의 수 중 소수를 찾는 문제입니다.

소수를 판단하는 방법은, 2부터 해당 수 - 1까지 나눠진다면 소수입니다.

 

소스코드

re = int(input())
nums = list(map(int,input().split()))
count = 0
for i in nums:
    if i == 1:
        continue
    if i == 2 or i == 3:
        count = count + 1
        continue

    check = False
    for j in range(2,i):
        if i%j == 0:
            check = True
            break;

    if check == False:
        count = count+1

print(count)

 

2부터, 해당 수 - 1 까지, 나눠지는 수가 있다면 이는 소수가 아닙니다.

check가 False 그대로일때 (나눠지는 수가 없음), count를 +1 만큼 합니다.

 

 

후기

코딩테스트를 하다보면 단골로 나오는 문제중 하나인 소수 문제입니다.

2부터 n-1 까지 나눠지는 수가 있는지 판단하는 방법으로 소수를 구할 수도 있지만,

매 수에 대해 2부터 n-1 까지 나눈다면 시간초과가 발생할 수 있어,

에라토스테네스의 채 등의 방법도 고려하면 좋습니다.