[BOJ/python] 1978번 소수 찾기

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

1978번: 소수 찾기

문제 해석

 

N 개의 수가 주어지고, 주어진 수들의 소수의 개수를 구하는 문제이다.

---

코드

input = __import__('sys').stdin.readline

n = int(input())
ans = 0
arr = list(map(int, input().split()))

for i in arr:
    if i < 2:
        continue
    flag = True
    j = 2
    while j * j <= i:
        if i % j == 0:
            flag = False
            break
        j += 1
    if flag:
        ans += 1
print(ans)

---

문제 풀이

 

소수를 체크하는 알고리즘은 간단하다.

소수는 1과 자기 자신을 제외한 수로만 이루어진 수이며, 1은 소수가 아니다.

따라서 소수 판별은 2부터 자기 자신 - 1까지의 모든 수를 나누었을 때 나누어지는 수가 없다면 그 수는 소수이다.

하지만 이는 너무 많은 연산을 해야 하기 때문에 자기 자신의 제곱근까지만 해보아도 소수 판별이 가능하다.

 

따라서 j = 2 부터 i까지 j^2이 i로 나누었을 때 나머지가 0이 나오는 경우가 있다면 flag를 False로 바꾸어 소수가 아니게 된다.

모든 경우의 수를 통과했다면 flag 는 참이므로 ans를 1 올리고 다음 배열의 수를 체크해나가면 된다.

 

원문

https://ddingmin00.tistory.com/24

[BOJ/python] 1978번 소수 찾기