[C] 백준 1929번 - 소수 구하기 (에라토스테네스의 체)

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

1929번: 소수 구하기

(21.08.26)

 

1929번: 소수 구하기 - C언어 풀이

 

[소스코드]

#include <stdio.h>
// [baekjoon] 1929번 - 소수 구하기

int main() {

	int num[1000001] = { 1,1, 0 };

	int m, n;

	scanf("%d %d", &m, &n);
	

	for (int i = 2; i <= n; i++) {
		if (num[i] == 0) {
			for (int j = 2; i*j <= n; j++) {
				num[i*j] = 1;
			}
		}
	}

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

n이 최대 1,000,000이라서
에라토스 테네스의 체 방법을 이용해야 하는 문제이다.​

최댓값 크기의 배열을 만들어 0으로 초기화한 다음,
소수가 아닌 수는 1을 대입하는 방식으로 지워나간다.​

에라토스테네스의 체 방법을 간단히 요약하면,
2부터 시작해서, 소수인 수의 배수를 다 지우면
남은 수가 소수가 된다.​

배수를 지울 때 코드를 잘못 짜서 헤맸었는데
for (int j = 2; i*j <= n; j++) {
num[i*j] = 1;
}

이런 식으로 배수만 찾아 지우는 반복문을 만들면 된다.