코드플러스 기초 - 1929번 (C++)

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

1929번: 소수 구하기

이전문제 

https://recording2memorize.tistory.com/10

코드플러스 기초 - 1978번 (c++)

 

처럼 풀면 시간초과에 걸린다.

 

 

이런 소수문제에서 쓰기 좋은 방법이 에라토스테네스 체 이다

https://donggoolosori.github.io/2020/10/16/eratos/

[Algorithm] 에라토스테네스의 체 - C++ - DGOS | 동꿀오소리

에라토스테네스 체에 대해 알지 못한다면 윗 글을 참고하자.

 

게속 오류나서 

https://dev-minji.tistory.com/56

[백준/C++] 1929번 : 소수 구하기(시간 초과, 에라토스테네스의 체)

여기를 참고해서 풀었음 세세하게 시간줄이는 법도 나와서 좋았다.

 

 

#include <iostream>
#include <cmath>
using namespace std;
 
int main(){
  int M, N;
  cin >> M >> N;
  bool isPrime[N+1];
  for(int i = 0 ; i<= N ; i++)
      isPrime[i] = true;
 
  isPrime[0] = false;
  isPrime[1] = false;
 
  for (int i=2; i<=sqrt(N); i++){
    if (isPrime[i] == true){
      for (int j = 2; j*i<=N; j++)
        isPrime[j*i] = false;
    }
  }
 
  for (int i=M; i<=N; i++){
    if (isPrime[i])
      cout << i << "\n";
  }
}