djswpsk1024   6년 전

#include <iostream>
#include <cstring>
using namespace std;
bool isPrime(int);
int main() {
    int min;
    int N, M, sum = 0, flag = 1;
    cin >> N >> M;
    for(int i = N; i <= M; ++i){
        if(isPrime(i)){
            sum += i;
        }
        if(flag == 1 && isPrime(i))
        {
            min = i;
            flag = 0;
        }
    }
    if(flag == 1)
        cout << -1;
    else
        cout << sum << endl << min << endl;
}
bool isPrime(int n){
    if(n < 2)
        return false;
    for(int i = 2 ; i < n; ++i){
        if(n%i == 0)
            return false;
    }
    return true;
}

djm03178   6년 전

루트 n까지만 검사해도 소수를 판별할 수 있습니다. 만일 루트 n을 넘는 약수가 존재한다면, 그 약수로 나눈 몫은 루트 n보다 작은 약수일 테니 이미 이전에 걸러졌어야 하니까요.

chogahui05   6년 전

is_prime 함수의 복잡도가 최악의 경우에 O(n)이니 오래 걸릴수밖에 없긴 해요.


대충 n이하의 소수 갯수는 n/logn 정도에 근사하는데요.

생각보다 djs님 코드가 오래 걸리지 않는 이유가

1부터 10000까지만 전수조사하면 되는 것도 있고요.


소수가 아닌 경우에 최대 O(root(n))만큼만 돌면 됩니다.

이걸 잘 풀어보면 대충..

(n-n/logn)*root(n) + n^2/logn 즈음 되는데요.

앞의 것은 대충 O(n루트n)정도. 뒤의 것은 O(n^2/logn)이라고 생각하면 되니까 실제 시간 복잡도는 O(n^2)가 아니라

O(n^2/logn) 정도고요.


소수가 아닌 경우에는 최악의 경우에나 루트 n이지.

그렇지 않은 경우에는 더 적은 루프로 끝나버리죠.. 자세한 건 소수 정리 참고해 보세요.

djswpsk1024   6년 전

답변 주신 분들 너무 고마워요!!!

댓글을 작성하려면 로그인해야 합니다.