백준 1978 : 소수찾기 (C++) (소수판별 알고리즘)

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

주어진 수들 중 소수의 개수를 출력한다.

예제 입력 1

4

1 3 5 7

예제 출력 1

3

 

접근 - 소수를 찾는 알고리즘 그냥 짜면 된다..

 

소수를 찾는 알고리즘에는 크게 2가지가 있다.

하나는 O(n)의 복잡도를 가지고 다른 하나는 O(√n)의 복잡도를 가진다.

 

1. O(n)의 복잡도를 가지는 알고리즘

void isprimenum(int num){
    if (num == 1)
        return;
    if (num == 2){
        prime++;
        return;
    }
    for(int i=2;i<num;i++){
        if(num%i == 0)  return;
    }
    prime++;
}

기본적인 소수판별 알고리즘이다.

 

void isprimenum(int num){
    if (num == 2){
        prime++;
        return;
    }
    if (num == 1 || num%2 ==0)
        return;
    
    for(int i=3;i<num;i+=2){
        if(num%i == 0)  return;
    }
    prime++;
}

n이 2이외의 짝수인 경우는 컷~해버려서 복잡도를 O(N/2)로 낮출수 있다.

하지만 나눠도 O(N)과 마찬가지 이므로 위 알고리즘도 조금낫다고 할 수 있겠다.

 

prime은 전역변수로 선언되어 있다.

 

2. O(√n)의 복잡도를 가지는 알고리즘

 

void isprimenum(int num){
    if (num < 2 )   return;
    for(int i=2;i*i<=num;i++){
        if(num%i == 0)  return;
    }
    prime++;
}

1부터 [√n]까지의 나눠서 0이아니면 소수이다.

만약 [√n] 이후에 나눠서 0이되는 수가 있다면 1~[√n] 사이의 수랑 곱해져서 n이 되는데,

그전에 필터링이 되지 않았다는 뜻이므로 이는 모순이다.

 

위와 마찬가지로 prime변수는 전역변수로 선언되어 있다.

소스코드

#include<iostream>
using namespace std;
int prime;
void isprimenum(int num){
    if (num < 2 )   return;
    for(int i=2;i*i<=num;i++){
        if(num%i == 0)  return;
    }
    prime++;
}
int main(){
    int N;
    cin>>N;
    for(int i=0;i<N;i++){
        int num;
        cin>>num;
        isprimenum(num);
    }
    cout<<prime;
}