소수 찾기 [C++]

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; }

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