백준 1929번
에라토스테스의 체 방법을 사용!
•
에라토스테스의 체
◦
에라토스테스의 체는 2부터 주어진 숫자보다 작은 배열에서
◦
가장 작은 수 부터 시작하여 반복한다
◦
그 수의 배수를 지워나간다
◦
지워지지 않은 남은 숫자는 모두 소수이다
1.
초기 배열을 다 0으로, 0과 1은 미리 1로
2.
2의 배수 다 1로
3.
3의 배수 다 1로
4.
남은 수는 소수
C
#include <stdio.h>
void op() {
int M, N;
int arr[10000001] = {0,};
arr[0] = 1, arr[1] = 1;
scanf("%d %d", &M, &N);
for (int i = 2; i <= N; i++) {
if (arr[i] == 1) continue;
else {
for (int j = 2; i * j <= N; j++)
arr[i * j] = 1;
}
}
for (int i = M; i <= N; i++) {
if (arr[i] == 0)
printf("%d\n", i);
}
return 0;
}
int main(void) {
op();
}
C
복사
C++
#include <iostream>
using namespace std;
#define MAX 1000000
int arr[MAX + 1]{ 0, };
int main() {
int m, n;
cin >> m >> n;
for (int i = 2; i <= n; i++) {
arr[i] = i;
}
for (int i = 2; i * i <= n; i++) {
if (arr[i] == 0) continue;
for (int j = i * i; j <= n; j = j + i) {
arr[j] = 0;
}
}
for (int i = m; i <= n; i++) {
if (arr[i] != 0) {
cout << arr[i] << '\n';
}
}
return 0;
}
C++
복사