[파이썬] 백준 1929 : 소수 구하기

[파이썬] 백준 1929 : 소수 구하기

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

1929번: 소수 구하기

실버 3

수학 정수론 소수판정 에라토스테네스의 체

---

소수는 1과 자기 자신을 제외한 수로 나누어 떨어지지 않는 수. (2는 소수)

 

에라토스테네스의 체 : 범위에서 합성수를 지우는 방식으로 소수를 찾는 방법.

1. 1은 제거

2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.

3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.

4. 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다.

5. (반복)

 

 

또한 입력한 수가 num일때, 그것을 나누는 수의 범위를 num의 제곱근까지의 값으로 제한하면 시간을 줄일 수 있음.

 

코드

def isPrime(num):
    if num == 1:
        return False
    else:
        for i in range(2, int(num**0.5) + 1):
            if num % i == 0:
                return False
        return True
 
 
M, N = map(int, input().split())
 
for i in range(M, N + 1):
    if isPrime(i):
        print(i)

입력 받은 두 값의 범위 내에서 소수를 판별한다.

(1이상 15이하)

해당 범위에서 1과 해당 수를 제외한 나머지 숫자로 나누어 떨어지면 소수가 아님을 판별한다.

 

2는 소수중에 유일한 짝수다.

2의 제곱근은 1.414...이므로

else:
        for i in range(2, int(num**0.5) + 1):
            if num % i == 0:
                return False
        return True

 

여기 반복문이 성립하지 않기 때문에 True를 반환한다.