[BOJ_C++] 1978번 : 소수 찾기

1. 문제

2. 풀이

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    bool isPrime[1001];
    memset(isPrime, true, sizeof(isPrime));
 
    // 에라토스테네스의 체 이용하여 1000까지의 소수 구하기
    isPrime[0] = false;
    isPrime[1] = false;
    for (int i = 2; i <= 1000; i++) {
        if (isPrime[i]) {
            // 소수의 N배수들은 모두 소수가 아님
            for (int j = 2 * i; j <= 1000; j += i)
                isPrime[j] = false;
        }
    }
    int num, input, result = 0;
    cin >> num;
    while(num--){
        cin >> input;
        if(isPrime[input])
            result++;
    }
    cout << result;
 
    return 0;
}

• 숫자가 1,000 이하의 자연수라고 하였으므로 isPrime 배열의 크기를 1,001로 선언해 주었다. 이때 1,001로 선언한 이유는 배열이 0부터 시작하기 때문에 1개 더 선언하여 배열의 인덱스가 숫자가 되는 형식으로 만들어 주기 때문이다.
• isPrime 배열을 모두 ture로 세팅하기 위해 memset을 이용하였고, 이중 for문을 사용하여 소수가 아닌 인덱스에 false를 넣어 주었다.
• while문을 돌며 input이 소수라면 result의 값을 1증가하는 방식으로 소수의 개수를 찾아주었다.
• result를 출력하여 프로그램을 종료하였다. 

3. 결과