소수 찾기

내가 작성한 코드

#include <iostream>
#include <numeric>
#include <iterator>

using namespace std;

int main() {
    int N;
    int arr[1001];
    int num;
    cin >> N;
    iota(begin(arr), end(arr), 0);
    arr[1] = 0;
    for (int i = 2; i <= 1000; ++i) {
        if (arr[i] != 0) {
            for (int j = i * 2; j <= 1000; j += i) {
                arr[j] = 0;
            }
        }
    }
    int answer = 0;
    for (int i = 0; i < N; ++i) {
        cin >> num;
        if (arr[num] != 0)
            answer++;
    }
    cout << answer << endl;
    return 0;
}

고민한 부분

어떻게 소수인지 식별할까?

1. 주어진 숫자를 2부터 순차적으로 나누어 나누어 떨어지는 수가 있는지 찾기
2. 1번의 방식으로 하되 2를 제외한 짝수를 배제하고 제곱근이 있는 수 배제하여 속도 올리기

위의 두 방식을 고려했을 때 나중에 수가 커지는 경우에 해당 수가 소수라면 결국에 불필요한 연산을 너무나도 많이 해야하는 불상사가 일어난다.

해결방법
DP방식으로 작은 크기의 소수를 찾고 소수의 배수는 제거하는 소거법 방식으로 구현하였다.
배열 내 인덱스에 맞는 수를 넣어줌으로 써 주어진 수를 1의 시간복잡도로 소수인지 아닌지 식별이 가능하도록 구현하였다

함수 설명

std::itoa() : 주어진 범위내에서 주어진 값을 순차적으로 증가시키며 넣어주는 함수이다.

결과