[백준] 1929.cpp : 소수 구하기

www.acmicpc.net/problem/1929

1929번: 소수 구하기

#include <iostream>

using namespace std;

int n, m;
int che[1000001] = {1, 1};

int main(void)
{
  ios_base::sync_with_stdio(0);
  cout.tie(0);
  cin >> n >> m;
  // 에라토스테네스의 체
  for(int i = 2 ; i < 1000001 ; i++)
  {
    if(che[i] == 1)
    {
      continue;
    }
    int idx = 2;
    while(i * idx <= 1000000)
    {
      che[i * idx++] = 1;
    }
  }

  for(int i = n ; i <= m ; i++)
  {
    if(!che[i]) cout << i << '\n';
  }
}

 

[Try]

1. 에라토스테네스의 체 사용했더니 너무 쉽게 풀었다.. 왜 실버2인거지??

 

[Point]

1. 백만개를 다 돌 필요 없이 최대 입력값 m 까지만 돌아도 됐을 것 같다.

2. 완전탐색 방식으로 전부 돌려도 성공이 뜨는 것 같다. 2초에 거의 근접하게 뜬다.

 

[More]