[알고리즘] 백준 1978번 "소수 찾기" (C/C++) - Don 임베디드

문제 요약:

주어진 자연수 N개 (a0, a1, a2 ... ,ai ... ,aN) 중 소수의 개수를 출력하는 프로그램을 작성하시오.

 

제약:

제한 시간 2초, 메모리 128MB,

N <= 100

ai <= 1000

예제 1 입력.	예제 1 출력.
4 1 3 5 7	3

 

정답 코드:

#include <iostream>
 
using namespace std;
void _InitValues(bool bPrimeArr[], int nSize);    // 에라토스테네스의 체 함수 선언.
 
int main()
{
    int N, nTmp;
    int nCount = 0;
    bool bIsPrime[1001];    // 어떤 자연수 k가 소수인지 여부 bIsPrime[k]
 
    // 에라토스테네스의 체 함수 호출.
    _InitValues(bIsPrime, 1000);
 
    // 총 입력될 숫자 개수.
    cin >> N;
 
    while (N-- > 0)
    {
        cin >> nTmp;
        if (bIsPrime[nTmp] == true)        // 소수인 경우 Count up.
        {
            nCount++;
        }
    }
    
    cout << nCount;
 
    return 0;
}
 
void _InitValues(bool bPrimeArr[], int nSize)
{
    // 에라토스테네스의 체. 범위가 정해진 자연수 중 소수를 걸러낸다.
    int nCurrentNum;
 
    for (int i = 0; i < 1001; i++)
    {
        bPrimeArr[i] = true;
    }
 
    // 1은 소수가 아님.
    bPrimeArr[1] = false;
 
    // 소수가 아닌 수들을 false 처리 해나간다.
    for (int j = 2; j <= (nSize / 2); j++)
    {
        if (bPrimeArr[j] == true)
        {
            // 소수인 경우, 자기 자신은 제외하고 시작.
            nCurrentNum = j * 2;
        }
        else
        {
            // 소수가 아닌 경우, 자기 자신부터 시작.
            nCurrentNum = j;
        }
 
        // 최대값에 도달할 때 까지 배수를 구하고, false 처리한다.
        while (nCurrentNum <= nSize)
        {
            bPrimeArr[nCurrentNum] = false;
            nCurrentNum += j;
        }
    }
}

원본 링크: https://www.acmicpc.net/problem/1978