백준 1978번 (C++)

www.acmicpc.net/problem/1978

1978번: 소수 찾기

 

<답안>

#include <iostream>
using namespace std;
int main()
{
    int n, temp;
    int array[1001] = {0};
    int input;
    int count = 0;
    
    array[2]=2;
    for(int i=2; i<=1000; i++)
    {
        for(int j=2; j<i; j++)
        {
            if(i%j == 0)
                break;
            else
            {
                if(j == i-1)
                    array[i] = i;
            }
        }
    }
    
    cin>>n;
    temp = n;
    while(n-- > 0)
    {
        cin>>input;
        if(array[input] != 0)
            count++;
    }
    
    cout<<count;
    
    return 0;
}

 

<설명>

입력된 숫자를 계속 소수인지 반복문을 돌리는 방법은

비효율적이고 오래걸리는 방법인 거 같아서

미리 1000까지 소수를 찾아놓고, 입력된 숫자가 소수인지만 판별하는 식으로 했다

 

인덱스 i=2 부터 i=1000까지 돌리며

만약 i 숫자를 2부터 i-1까지 나눈 나머지 값을 비교하였을때

나눠지는 경우는 배수가 존재하기 때문에 소수가 아니므로 break

그 외의 경우 중 i-1까지 배수가 아닌 경우는 소수가 맞으므로

그 소수를 인덱스로 하여 array[소수] = 소수 로 변경해 놓는다

 

그리고서 반복해서 입력된 수에 따라 array[입력수] 값이 0이 아니면 소수이기에

count를 증가시킨다

최종적으로 count를 출력시킨다