백준 2581 소수

문제링크 : https://www.acmicpc.net/problem/2581

아이디어

• 소수구하는방법 1 : 2~sqrt(N)까지 나눠서 구할 수 있음
  • 시간복잡도 : O(N^1/2)
• 소수 더 빨리 구하는법 : 에라토스테네스의 채
  • 2부터 원하는 숫자까지
  • 숫자를 배수가 되게 더해가면서 체크를해줌(이 수는 소수가 아님)
  • 처음에 체크가 되어있지 않은 수는 소수이므로 별도로 체크
  • 시간복잡도 : O(NlgNlgN)
• 소수를 에라토스테네스의 채로 미리 구해놓을떄
• M보다 클경우, 소수의 합을 구하고, 최솟값 출력

시간복잡도 계산

• 소수구하면서 합, 최솟값 구함 : O(NlgNlgN)

자료구조

• 이미 지나간것 체크 : bool chk
• 소수 합 : 최대 1e4 * 1e4 > INT 가능

코드(C++)

#include <iostream>
 
using namespace std;
 
bool chk[10010];
int main() {
    fill(chk, chk+10010, 0);
    
    int M,N; cin >> M >> N;
    
    int sumv= 0;
    int minv = 10010;
    for(int i=2; i<=N; i++) {
        // 소수일때
        if(chk[i] == 0) {
            chk[i] = 1;
            // M보다 크다면
            if(i>=M) {
                sumv += i;
                minv = min(minv, i);
            }
        }
        
        int cur = i;
        while(cur<=N) {
            chk[cur] = 1;
            cur += i;
        }
    }
    
    if(sumv == 0) cout << -1 << '\n';
    else {
        cout << sumv << '\n';
        cout << minv << '\n';
    }
    return 0;
}
 

문제유형

• 에라토스테네스의 채
  • 일반적으로 소수인지 확인할떄 2부터 sqrt(N)까지 확인 >> N * sqrt(N) >> 시간초과
  • 소수 개수 NlglgN으로 구할수 있음
  • 각 배수를 체크해주고, 그 배수 오면 넘어가는 방법