[C] 1929번: 소수 구하기
[C] 1929번: 소수 구하기
문제
https://www.acmicpc.net/problem/1929
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
출력
한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.
풀이
에라토스테네스의 체를 사용합니다.
is_not_prime[i] == 1이면 소수가 아님is_not_prime[i] == 0이면 소수- 2부터 시작해 각 수의 배수를 지워 나갑니다
- 마지막에 M부터 N까지 확인하며 소수만 출력하면 됩니다
이미 더 작은 수의 배수로 지워진 값은 다시 처리할 필요가 없으므로, 현재 값이 아직 소수일 때만 배수를 지우면 됩니다.
코드
#include <stdio.h>
int main() { int M, N; static int is_not_prime[1000001] = {0};
scanf("%d %d", &M, &N);
is_not_prime[0] = 1; is_not_prime[1] = 1;
for (int i = 2; i * i <= N; i++) { if (!is_not_prime[i]) { for (int j = i * i; j <= N; j += i) { is_not_prime[j] = 1; } } }
for (int i = M; i <= N; i++) { if (!is_not_prime[i]) { printf("%d\n", i); } }
return 0;}