프로그래머스 2024.01.16 (1Lv 소수 찾기)

문제

---

문제 설명
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건
   ◈ n은 2이상 1000000이하의 자연수입니다.

입출력 예

n	result
10	4
5	3

입출력 예 설명
입출력 예 #1
1부터 10사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

코딩

---

#include <string>
#include <vector>

using namespace std;

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

    vector<bool> vec_table(n + 1, true);
    //vec_table.resize(n + 1);

    for (int i = 2; i < vec_table.size(); ++i)
    {
        if (vec_table[i])
        {
            answer++;
            int imul = 2;
            for (int j = i; j < vec_table.size();)
            {
                if (imul * i < vec_table.size())
                {
                    vec_table[i * imul] = false;
                }

                imul++;
                j = i * imul;
            }
        }
        else
            continue;
    }

    return answer;
}

 

해당 문제는 에라토스테네스의 체를 이용해 풀었다.

가장 먼저 주어진 수 n만큼 배열을 만들어, 배열의 크기만큼 반복수행 해 이번 검사하는 idx가 true가 들어있다면, 해당 idx의 배수들의 idx에 접근해 false로 변경해주며 풀었다.

 

이후 해당 문제는 소수를 배열로 묶어 반환하는게 아닌, 소수의 개수를 반환하면 되기 때문에 단순히 answer를 증가시키며 해를 구해주었다.

 

array가 아닌 vector를 사용한 이유는 array의 크기를 정할때는 변수를 사용할 수 없기 때문에 vector를 이용해 주었으며, bool값을 이용해 이전 체크했던 수의 배수였던 것 즉, 소수가 아닌 수들을 체크해주며 풀었다.

 

코드가 깔끔하게 나오지는 않은것 같아 불만족스러웠다.

 

#include <string>
#include <vector>

using namespace std;

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

    vector<bool> vec_table(n + 1, true);

    for (int i = 2; i < vec_table.size(); ++i)
    {
        if (!vec_table[i])
            continue;

        answer++;
        int imul = 2;
        for (int j = imul * i; j < vec_table.size(); j = imul * i)
        {
            imul++;
            if (vec_table[j])
                vec_table[j] = false;
            else
                continue;
        }
    }

    return answer;
}

때문에 코드를 조금 정리해 다시 짰다.

실행 결과

---