백준 | 1929. 소수 구하기

소수를 먼저 구해야할거같은데

소수 구하는 함수를 만들어서 소수를 stack에 넣어서

나눠지면 합성수 안나눠지고 stack 끝까지 가면 소수니까

int prime(stack<int>s, int num){
    while(!s.empty()){ // 스택이 빌 때까지 돌기
        if(num % s.top() == 0) return 0; // 중간에 나누어 떨어지는 애 나오면 큰 함수 끝내기(합성수)
        s.pop(); /
    } // 스택 빌 때까지 돌면 나누어떨어지는게 없다는거니까 소수임
    return 1;
}

이런 식으로 함수를 짤 수 있음.

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

int prime(stack<int>s, int num){
    while(!s.empty()){
        if(num % s.top() == 0) return 0;
        s.pop();
    }
    return 1;
}

int main(){
    int n, m;
    cin >> n >> m;
    stack<int>s;
    s.push(2);

    for(int i = 3; i<=m; i++){
        int p = prime(s, i);
        if(p){
            s.push(i);
            if(i>=n) cout << i << "\n";
        }
    }
}

 

이렇게 하니까 시간 초과 나온다,,,, 젠장

(1 ≤ M ≤ N ≤ 1,000,000) 범위가 이래버려서 그런듯..

 

에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘 활용해야될거같은데

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

int main(){
    int n, m;
    cin >> n >> m;
    vector<bool>p(m+1,1); // 전부 소수라고 가정
    p[0] = 0, p[1] = 0;
    
    for(int i = 2; i*i<=m; ++i){
        // 합성수는 두 수의 곱으로 표현할 수 있는데,
        // 두 수 모두 가장 큰 수로 표현되려면 제곱수밖에 없음.
        // 더 큰 수는 반드시 더 작은 수로 이미 나누어짐.
        if(p[i]){
            for(int j= i*i; j<=m; j+=i){
                // 2=> 소수, 3=> 소수. 얘네 건너 뛰고 합성수 표시하려면
                // 제곱한 수부터 시작해야함.
                p[j] = 0;
            }
        }
    }

    for(int i = n; i<=m; ++i){
        if(p[i]) cout << i << "\n";
    }
}

이러면 이전에 비해 시간복잡도도 훨씬 줄어들고 간단하게 풀 수 있음!!