문제
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.
- 입력
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
- 출력
한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.
- 예제 입력 1
3 16
- 예제 출력 1
3 5 7 11 13
- 첫번째 시도
m, n = map(int, input().split()) sosu = [] for num in range(m,n+1): errorFlag = 0 if num > 1: for i in range(2,num): if num % i == 0: errorFlag += 1 break if errorFlag == 0: sosu.append(num) for answer in sosu: print(answer)
- 정답
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은 소수가 아니므로 제외해준다. 반복문을 돌린다. 범위는 2부터 int(i**0.5)+1까지이다. 특정 수의 제곱근을 구해, 그 제곱근까지의 약수를 구하면 해당 약수를 포함하는 수를 모두 제거할 수 있다(소수가 아니기에). 이렇기 때문에 범위를 위와같이 설정해주었다. 예를들어, i=12에서 12의 약수는 1 2 3 4 6 12 int(sqrt(12))=3이고 12는 3으로 나누어 떨어지므로 더 검사할 필요가 없다. i가 j로 나누어떨어지므로 약수가 존재한다. 고로 소수가 아니고, 해당 제곱근(j)이상의 숫자에 대해 더이상 검사할 필요가 없으므로 멈춘다. i가 1이 아니라면 해당 숫자를 출력해준다.
에라토스테네스의 체
에라토스테네스의 체에서는 1을 제거 --> 지워지지 않는 수 중에 제일 작은 2를 소수로 선택한다 --> 나머지 2의 배수를 모두 지운다 --> 지워지지 않는 수 중에 제일 작은 3을 소수로 선택한다 --> 나머지 3의 배수를 지운다 ... 5, 7, 11, 13 등으로 반복을 한다. 이런 식으로 처리가 되고, 이런 일련의 과정을 해나가면 다음과 같이 나온다.