[백준/C] 1929번

Q) 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력이 주어지고 그 사이의 소수를 한 줄씩 출력해라.

입력	출력
3 16	3
	5
	7
	11
	13

A) 알고리즘

[ 소수 구하는 최적의 알고리즘 ]

• 에라스토테네스의 체
  2부터 소수를 구하고자 하는 모든 수를 나열한 뒤, 특정 수의 배수들을 제거해 나가는 알고리즘

• c언어

#include "stdio.h"

int main()
{
  int M, N;
  //index로 소수 판별 - 소수면 0, 소수가 아니면 1 채우기
  //arr[1]=1로 채움
  int arr[1000001] = {0,1};
  scanf("%d %d", &M, &N);

  //N까지 i*j로 특정 수의 배수를 찾고 그 수는 1로 채움
  for(int i=2; i<=N; i++){
    for(int j=2; i*j<=N; j++){
      arr[i*j]=1;
    }
  } 
  
  for(int k=M; k<=N; k++){
    //값이 0인 위치만 출력
    if(!arr[k]){
      printf("%d\n",k);
    }
  }

  return 0;
}