코딩테스트/프로그래머스
[Level 1][C++] 소수 찾기
MJ.Lee
2024. 10. 10. 22:38
#include <string>
#include <vector>
#include <cmath>
using namespace std;
int solution(int n) {
bool *arr = new bool[n + 1];
int answer = 0;
for (int i = 0; i < n + 1; i++)
arr[i] = true;
for (int i = 2; i <= sqrt(n); i++)
{
if (!arr[i])
continue;
for (int j = i * i; j <= n; j += i)
arr[j] = false;
}
for (int i = 2; i < n + 1; i++)
if (arr[i])
answer++;
return answer;
}