C++ - 소수 판별 / 단순 브루트포스, 에라토스테네스의 체

문제 1 : https://www.acmicpc.net/problem/2581

2581번: 소수

해당 문제는 범위가 10,000 이하의 자연수이며 시작값과 끝값 중에 존재하는 소수를 모두 더한 값과 최솟값을 출력하면 된다.

따라서 단순 브루트포스로 isPrime 함수를 구현한다. 1과 n이 아닌 다른 값으로 나누어 떨어지면 false를 반환, 그렇지 않다면 소수이므로
true를 반환한다. 이렇게 소수를 판별할 수 있고, 소수로 판별된 값은 total에 모두 더하며 최솟값을 계속 갱신해준다.

#include <iostream>
using namespace std;

bool isPrime(int n){
    if(n==1) return false;

    for(int i=2; i<n; i++){
        if(n%i == 0) return false;
    }

    return true;
}

int main(){
    int s, e; //start & end
    int total = 0, minVal = 10001;
    cin >> s >> e;

    for(int i=s; i<=e; i++){
        if(isPrime(i) == true){
            total += i;
            if(minVal > i){
                minVal = i;
            }
        }
    }

    if(minVal == 10001 && total == 0){
        cout << -1;
        return 0;
    }

    cout << total << '\n' << minVal;
}

 

문제 2 : https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

이번 문제는 앞의 문제와 비슷하지만 범위가 1,000,000까지이므로 단순 브루트포스로는 시간초과가 난다.

따라서, 에라토스테네스의 체를 사용한다.

 

에라토스테네스의 체를 간단히 설명하자면 소수는 소수인 채로 냅두고 해당 소수의 배수를 모두 지운다.

 

주로 2부터 시작하는데 2는 소수이므로 2의 배수를 모두 지우고 다음 자연수로 넘어가

소수인 3의 배수를 지우고, 4는 이미 지워졌으므로 continue, 5도 소수이므로 5의 배수를 지우고, 하다보면 소수만 남게 된다.

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

#define MAX 1000000

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    int s, e;
    int nums[1000001];
    cin >> s >> e;

    for(int i=2; i<=MAX; i++){
        nums[i] = i;
    }

    for(int i=2; i<=sqrt(MAX); i++){//j for문에서 i의 제곱부터 배수를 지우므로
    //범위의 제곱근까지만 구하면 된다.
        if(nums[i] == 0) continue;

        for(int j = i * i; j<=MAX; j+=i){
            nums[j] = 0;
        }//소수인 i는 냅두고 i의 배수를 모두 지운다.
        //2라면 4부터 6, 8 .. 을 지우고 3이라면 9부터 12, 15, ..
    }

    for(int i=s; i<=e; i++){
        if(nums[i] != 0){
            cout << nums[i] << '\n';
        }
    }
}