[백준 1929] 소수 구하기 C언어 / 에라토스테네스의 체

문제

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

1929번: 소수 구하기

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
void input(int a[], int n)
{
	a[0] = 0;
	for (int i = 0; i < n; i++)
		a[i + 1] = i + 1;
}
int main(void)
{
	int m, n;
	int* sosu = (int*)malloc(sizeof(int) * 1000001);

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

	input(sosu, 1000000);

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

		if (i * i >= n) // for문 맨 뒤로 보냄, 반례 3 4
			break;
	}

	sosu[1] = 0; // 따로 처리
	for (int i = m; i <= n; i++) {
		if (sosu[i] != 0)
			printf("%d\n", sosu[i]);
	}

	free(sosu);

	return 0;
}

풀이

에라토스테네스의 체

그리스의 수학자이자 지리학자인 에라토스테네스가 고안한 소수(素數)를 찾는 방법으로, 이 방법으로 소수를 찾으려면, 2부터 시작해 자연수를 차례로 쓴 다음, 2 이외의 2의 배수, 3 이외의 3의 배수, 5 이외의 5의 배수의 순서로 수를 지워나가 끝에 남는 수가 소수이다.

 

1. 2외의 2의 배수를 지운다(p=2). 이때 2가 최초의 소수
2. 그 다음 소수인 3을 제외한 3의 배수 (p=3)를 제거
3. 이 방법을 다음에 지울 소수, 즉 p의 제곱이 n보다 커질 때까지 이 방법을 계속한다. (p^2>=n)

[네이버 지식백과] 에라토스테네스의 체 [Eratosthenes' sieve] (두산백과 두피디아, 두산백과)