[백준][C++]1929번 소수 구하기

문제

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

1929번: 소수 구하기

 

 

풀이

에라토스테네스의 체 알고리즘

에라토스테네스의 체 알고리즘

 

 

코드

#include <iostream>
#include <vector>
using namespace std;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int M, N;
  cin >> M >> N;

  vector<bool> prime(N + 1, true);	// 처음에는 모든 수가 소수(true)인 것으로 초기화
  prime[0] = false;
  prime[1] = false;	// 1은 소수가 아님
  
  for(int i = 2; i <= N; i++)
  {
    if(prime[i])	// i가 소수인 경우
    {
      int j = 2;
      while(i * j <= N)
      {
        prime[i * j] = false;	// 배수 지우기
        j++;
      }
    }
  }

  // 배열 prime에서 소수 값 출력
  for(int i = M; i <= N; i++)
  {
    if(prime[i])
    {
      cout << i << "\n";
    }
  }

  return 0;
}