본문으로 바로가기
#include <cstdio>

const int N = 1000000000;// 10억
int prime[N+1];

void getPrime(int);

int main(int argc, const char * argv[]) {
  int n;
  scanf("%d", &n);
  getPrime(n);
  for(int i=2 ; i<=n ; i++){
    if(prime[i] == 0)
      printf("%d ", i);
  }
  puts("");
  return 0;
}

void getPrime(int n){
  for(int i=2 ; i<=n ; i++){// 최소 소수인 2부터 시작
    if(prime[i] == -1) continue;// 소수의 배수일 경우 무시
    for(int j=2 ; j<=n/i ; j++)
      prime[i*j] = -1;// 소수의 배수는 -1 값을 할당
  }
}

댓글을 달아 주세요