Level 0. 합성수 찾기

Level 0. 합성수 찾기

 

 

에라토스테네스의 체를 활용해 해결했다.

 

2부터 소수인 수는 자신을 제외한 자신의 배수들을 합성수로 표시하는 알고리즘이다.

 

가장 작은 소수는 2이기 때문에 last(n / 2)까지만 반복문을 수행하면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int n)
{
    int last = n / 2;
    vector<bool> v(n + 1, true);

    for (int i = 2; i <= last; ++i)
        if (v[i])
            for (int j = 2 * i; j <= n; j += i)
                v[j] = false;

    return count(v.begin() + 1, v.begin() + n + 1, false);
}

 

위 풀이는 last(n / 2)까지 반목문을 수행하고 마지막에 count를 순회하면서 n번 또 접근한다.

 

아래 풀이는 애초에 n까지 반목문을 수행하며 정답을 구하는 풀이이다.

 

#include <iostream>
#include <vector>

using namespace std;

int solution(int n)
{
    int answer = 0;
    vector<bool> v(n + 1, true);

    for (int i = 2; i <= n; ++i)
        if (v[i])
            for (int j = 2 * i; j <= n; j += i)
                v[j] = false;
        else
            ++answer;

    return answer;
}