[프로그래머스] 프로그래머스 Level1 소수 찾기 C++

문제

https://programmers.co.kr/learn/courses/30/lessons/12921?language=cpp 

코딩테스트 연습 - 소수 찾기

풀이

알고리즘 문제에서 많이 나오는 소수 찾기 문제이다.

판별해야 하는 범위가 1 ~ n인데 n이 최대 1000000이므로 일반적인 소수 판별로는 시간 초과가 날 것이다. 필자는 에라토스테네스의 체로 접근하여서 문제를 해결할 수 있었다.

0, 1은 소수가 아니므로 처음부터 제외시켰고 바깥 for문의 범위를 n의 제곱근만큼만 지정해주었다.

왜냐하면 안쪽의 for문을 통해서 i가 소수가 아니면 i + i, i + i + i도 소수가 아님을 판별할 수 있기 때문이다. 

코드

#include <string>
#include <vector>
#include <cmath>

using namespace std;

int isPrimeNum[1000001];

int solution(int n) {
    int answer = 0;

    for (int i = 2; i <= n; i++)
    {
        isPrimeNum[i] = i;
    }

    for (int i = 2; i <= sqrt(n); i++)
    {
        for (int j = i + i; j <= n; j += i)
        {
            isPrimeNum[j] = 0;
        }
    }

    for (int i = 2; i <= n; i++)
    {
        if (isPrimeNum[i] != 0)
        {
            answer++;
        }
    }

    return answer;
}