[백준/BOJ] 1929번 소수 구하기 (C/C++)

백준 온라인 저지(BOJ) 1929번 소수 구하기

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

1929번: 소수 구하기

* 사용언어 : C언어, C++

 

1. 문제

M 이상 N 이하의 소수를 모두 출력 (M, N은 최대 1,000,000)

 

2. 풀이

에라토스테네스의 체를 활용하여

N 이하의 소수를 모두 찾은 후 출력하는 방식을 사용했습니다.

 

에라토스테네스의 체를 사용할 때 for문의 max값은

1,000,000이 아닌 1,000(루트 1,000,000)까지만 진행하면 됩니다. 

[에라토스테네스의 체 사용 시 루트 n까지만 진행해도 되는 이유]
만약 어떤 수 n이 1과 n이 아닌 다른 수로 나누어 떨어진다면 n은 a * b로 표현할 수 있습니다.
이 때 a가 루트 n보다 크거나 같다면, b는 루트 n보다 작거나 같게 됩니다.

따라서 루트 n보다 작은 b만으로 에라토스테네스의 체를 사용하더라도
n 이하의 모든 소수가 아닌 수를 잡아낼 수 있게 됩니다.

 
이후 설명은 아래 코드로 대체하겠습니다.

 

 

추가로 제출 시 93%에서 오답이 된다면 1에 대한 처리를 해주시면 됩니다.

1은 소수도 합성수도 아니기 때문에 출력하면 안됩니다.

(ex. 입력 1 3 -> 정답 2 3)

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
1929_소수 구하기
5016KB	16ms
*/
#include <cstdio>

const int LM = 1000001;
int isNotPrime[LM], m, n;

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d %d", &m, &n);
	
	isNotPrime[1] = 1;
	for (int i = 2; i < 1000; ++i) {
		if (isNotPrime[i]) continue;

		int idx = i * 2;
		while (idx <= n) {
			isNotPrime[idx] = 1;
			idx += i;
		}
	}

	for (int i = m; i <= n; ++i) {
		if (!isNotPrime[i]) printf("%d\n", i);
	}
	return 0;
}

* 첫 번째 for문에서 i를 1000까지가 아닌 sqrt(n) + 1까지 진행해도 정답이 됩니다.