2018~2019/Level 1

소수 찾기 [C++]

전기도둑 2018. 10. 1. 22:39 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <vector>
#include <cmath>

using namespace std;

long long solution(int N) {
    long long answer = 0;
    bool *numbers = new bool[N+1];

    for(int i=2; i<=N; i++)
        numbers[i] = true;

    for(int i=2; (i*i)<=N; i++) {
        if(numbers[i])
        {
            for(int j=(i*i); j<=N; j+=i) {
                numbers[j] = false;
            }
        }
    }

    for(int i=2; i<=N; i++)
    {
        if(numbers[i])
        {
            answer++;
        }
    }

    return answer;
}


- 에라토스테네스의 체를 이용하여 소수를 구한다.

저작자표시 비영리 변경금지