(c++)백준 1929번: 소수 구하기

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

1929번: 소수 구하기

[풀이]

소수는 에라토스테네스의 체 알고리즘을 이용하여 구하였다.

에라토스테네스의 체 알고리즘은 2부터 구하고자 하는 범위의 수들을 배열에 넣어 소수가 아닌 수를 체크하는 알고리즘이다.

2를 제외한 2로 나누어 떨어지는 값 체크 → 3을 제외한 3으로 나누어 떨어지는 값 체크 → (4는 이미 체크 되었으므로 패스) → 5를 제외한 5로 나누어 떨어지는 값 체크 → ··· 마지막까지 체크되지 않은 값들이 소수이다.

 

2를 제외한 2로 나누어 떨어지는 값 체크

 

2	3	4	5
6	7	8	9
10	11	12	13

 

3을 제외한 3으로 나누어 떨어지는 값 체크

2	3	4	5
6	7	8	9
10	11	12	13

 

5를 제외한 5로 나누어 떨어지는 값 체크

2	3	4	5
6	7	8	9
10	11	12	13

· · ·

∴ 2부터 13까지 소수는 2, 3, 5, 7, 11, 13

 

※소수를 출력할 때 cout을 썼더니 시간초과가 나와서 printf를 사용하였다.

 

#include <iostream>
#include <cstdio>//printf
using namespace std;
#define Max 1000001

int M, N;
int check[Max] = { 0, };//소수 아니면 -1

//에라토스테네스의 체
void getPrime() {
	for (int i = 2; i < N; i++) {
		if (check[i] == -1)continue;
		for (int j = i + i; j <= N; j += i) {
			if (check[j] == -1)continue;
			if (i == j)continue;
			check[j] = -1;
		}
	}
}

void solution() {
	cin >> M >> N;
	if (M == 1)check[1] = -1;//1은 소수 아님

	getPrime();
	for (int i = M; i <= N; i++) {
		if (check[i] != -1)
			printf("%d\n", i);
	}
}

int main() {
	solution();
	return 0;
}