[백] 43446 소수 구하기 - 에라토스 뭐?

에라토스테네스의 체의 핵심은 걸러진 수는 체로도 사용을 안 한다는 것이다.

뭘 자꾸 거른다길래 2, 3, 4, 5, ... 다 거르다가는 시간 초과라는 낭패를 볼 수 있다.

4는 2의 배수이기 때문에 4의 배수는 자연히 2의 배수다.

따라서 2의 배수를 다 걸렀다면 4의 배수를 거르는 것은 시간 낭비인 것이다.

#define _CRT_SECURE_NO_WARNINGS


#include <stdio.h>

#include <malloc.h>


int main()

{

  int M, N, i, j;

  scanf("%d %d", &M, &N);

  int *sosu = malloc(sizeof(int)*(N + 1));

  for (i = 2; i <= N; i++) sosu[i] = i; //소수인지 표시 남기는 배열

  sosu[0] = 0;

  sosu[1] = 0; //0과 1은 소수가 아님


  for (i = 2; i <= N; i++)

  	if (sosu[i]) //만약 이때까지 걸러지지 않았으면 소수!

  		for (j = i+i; j <= N; j += i) sosu[j] = 0;//소수의 배수는 소수가 아님


  for (i = M; i <= N; i++) if (sosu[i]) printf("%d\n", i);


  for (int i = 0; i < 3; i++) getchar();

  return 0;

}