소수 - 백준 1978 [Python]

소수의 조건

• 약수가 1과 자기 자신 밖에 없는 수
• N이 소수가 되려면, 2보다 크거나 같고, N-1보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

소수를 구하는 방법

1. 어떤 수 N이 소수인지 아닌지?
2. N이하의 모든 소수를 구하는 방법

1. 어떤 수 N이 소수인지 아닌지? : 소수의 정의를 이용하는 방법, 약수의 특징을 이용하는 방법, 2~루트N까지 나누어 떨어지는지 (약수가 있는지 판별) 검사해 보는 방법이 있다.

 

이때, 직접 루트N을 구하는 것이 아니라, 값을 찾을 때 i = 2 - 루트N이기 때문에 i제곱이 N보다 작거나 같다는 범위를 사용하여 문제를 해결한다. (실수는 근사값이기 때문에, 정수의 표현을 사용하는 것이 안전)

 

Example)

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

1978번: 소수 찾기

Solution)

 

def is_prime(x):
    if x<2:
        return False
    i = 2
    while i*i <=x:
        if x%i == 0:
            return False
        i+=1
    return True

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

for x in a:
    if is_prime(x):
        ans +=1
print(ans)