12921. 소수 찾기

시간 복잡도: O(N lg lgN)

에라토스테네스의 체

1#include <bits/stdc++.h>
2using namespace std;
3
4int solution(int n) {
5  vector<int> sieve(n+1, true);
6  sieve[0] = sieve[1] = false;
7  int cnt = 0;
8
9  for(int i=2; i<=n; ++i) {
10    if(!sieve[i]) continue;
11
12    for(int j=i+i;j<=n;j+=i) {
13      sieve[j] = false;
14    }
15
16    ++cnt;
17  }
18
19  return cnt;
20}

아래와 같이 구하는 방법도 있다.

시간 복잡도: O(N sqrt N)

1#include <string>
2#include <vector>
3
4using namespace std;
5
6bool isPrime(int n) {
7    if(n<2) return 0;
8    if(n<4) return 1;
9    
10    if((n&1)==0 || n%3==0) return  0;
11    
12    
13    for(int i=5; i*i<=n; i+=6) 
14        if(n%i==0 || n%(i+2)==0) return 0;
15    return 1;
16}
17int solution(int n) {
18    int answer = 1;
19    if(n<2) return 0;
20    if(n==2) return 1;
21    for(int i=3; i<=n; i+=2) {
22        if(isPrime(i)) ++answer;
23    }
24
25    return answer;
26}