[백준] 소수 찾기 (C++)

 

문제 URL:

www.acmicpc.net/problem/1978

1978번: 소수 찾기

 

다음 문제는 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램으로

함수를 이용하여 소수를 찾는 코드를 따로 작성해주었다.

 

소수는 1과 자기 자신 만으로만 나누어져야 하기 때문에 1과 자기 자신 사이의 수로 나누었을 때

나누어진다면 그 수는 소수가 아니게 된다. 

 

여기서 중요한 점은 굳이 두 수(1과 자기 자신) 사이에 있는 모든 수로 나누어줄 필요가 없다는 점이다.

주어진 수가 n이라고 했을 때 소수를 판단하기 위해서는 2부터 √n까지만 확인하면 된다. 

 

위 내용에 따라서 sig = 0일 때를 소수인 경우, sig = 1일 때를 소수가 아닌 경우로 두고,

만약 1과 n 사이의 어떤 수 i(i<=√n)로 나누었을 때 나머지가 0이라면 주어진 n은 소수가 아니기 때문에

sig에 1을 대입해주었다. 

---

#include<iostream>
using namespace std;

int f(int n)
{
    int sig = 0;
    if(n==1)
        sig = 1;
    
    for(int i=2; i*i<=n; i++)
    {
        int result = n%i;
        if(result==0)        //나머지가 0-> i로 나누어 떨어짐, 소수X
        {
            sig = 1;
            break;
        }
    }
    
    return sig;            //sig==1-> 소수X, sig==0-> 소수
}

int main()
{
    int t, n, count=0;
    cin >> t;
    for(int i=0; i<t; i++)
    {
        cin >> n;
        if(f(n)==0)
            count++;
    }
    
    cout << count;
}