개요

https://www.acmicpc.net/problem/1929
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

접근 방식

1. 예전에 에라스토테네스의 체를 공부한 적이 있어 적용을 했으나 시간 초과가 나와서 당황했다.

bool isPrime(int N){
    if(N==1) return false;
    for(int i=2;i<=N/2;i++){
        if(N%i==0){
            return false;
        }
    }
    return true;
}

2. 문제는 잘못 기억하고 있어서 발생한 시간 초과였다.
   N을 2로 나눈 값까지가 반복이 아니라
   약수 개념이므로 당연히 제곱근값까지 반복해야한다.

 //for(int i=2;i<=N/2;i++){
 for(int i=2;i<=sqrt(N/2);i++){

전체 코드

#include<iostream>
#include<math.h>
using namespace std;


bool isPrime(int N){
    if(N==1) return false;
    
    for(int i=2;i<=sqrt(N);i++){
        if(N%i==0){
            return false;
        }
    }
    return true;
}

int main(){

    int M, N;
    cin >> M >> N;
    for (int i = M; i <= N; i++)
    {
        if (isPrime(i))
        {
            cout << i << "\n";
        }
    }
}

개선 시도

조금이라도 더 시간을 줄여보고자 다른 방법으로 시도해봤다.
100만 배열을 선언한 후,
미리 2부터 11까지 배수들을 전부 체크했다.

bool prime[1'000'000];

void initNum(){
    prime[1]=false;
    for (int i = 2; i <= 11; i++)
    {
        for(int j=2;i*j <= 1'000'000;j++){
            if(!prime[i*j]) continue;
            prime[i*j]=false;
        }
    }
    
}

그 후, isPrime함수를 거치기 전에 미리 배수인지 체크하는 식으로 걸렀다.

   for (int i = M; i <= N; i++)
    {
        if (!prime[i])
            continue;
        if (isPrime(i))
        {
            cout << i << "\n";
        }
    }

시도한 후 시간은

8ms정도 줄었다,,

개선 코드

#include<iostream>
#include<math.h>
using namespace std;

bool prime[1'000'000];

bool isPrime(int N){
    for(int i=2;i<=sqrt(N);i++){
        if(N%i==0){
            return false;
        }
    }
    return true;
}

void initNum(){
    prime[1]=false;
    for (int i = 2; i <= 11; i++)
    {
        for(int j=2;i*j <= 1'000'000;j++){
            if(!prime[i*j]) continue;
            prime[i*j]=false;
        }
    }
    
}

int main(){
    fill(prime,prime+1'000'000,true);
    initNum();

    int M, N;
    cin >> M >> N;
    for (int i = M; i <= N; i++)
    {
        if (!prime[i])
            continue;
        if (isPrime(i))
        {
            cout << i << "\n";
        }
    }
}