[BOJ/C++] 1978. 소수 찾기

https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

문제

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

입력

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

출력

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

풀이 방법

1. 소수 찾기 알고리즘은 다음과 같이 진행할 수 있다.

a. Brute Force (O(N))

 - 2부터 N - 1까지 반복해서 N이 나눠지는 수가 있다면 소수가 아닌 것으로 판정하는 알고리즘이다.

bool isPrimeNumber(int n)
{
    for (int i = 2; i < n; i++)
    {
    	if (n % i == 0)
        	return false;
    }
    return true;
}

이런식으로 표현할 수 있다.

 

하지만 우리는 이것을 개선할 수 있다.

 

O(n^(1/2)) 루트 알고리즘으로 말이다.

 

b. O(N^(1/2)

 

이 원리는 다음과 같다.

보기에 헷갈릴 수도 있지만 노란색은 '소수'인 수이고 빨간색은 '소수가 불가능한 수'이다.

그리고 파란색은 소수가 안되는 이유가 되는 원인인 수이다.

 

아래에 서식을 보면 알 수 있지만 4의 경우 [2, 2], 6의 경우엔 [2, 3] or [3, 2], 8의 경우에는 [2, 4], [4, 2] 이와 같은 순서쌍을 이루게 된다.

 

고로 순서쌍의 뒤에오는 수까지 검증할 필요가 없다는 것이다.

그렇다면 순서쌍의 앞의 수를 구하기 위한 Range(범위는 어떻게 생각해야 될까?)

-> 4, 9 Case를 보면 알 수 있듯이 제곱수일 때 자신과 곱해서 된다는 것을 알 수 있다.

제곱수만큼만 소수인지 판별하게 되면 그 수가 소수인지 아닌지 알 수 있다는 것이다.

 

제곱수만큼만 범위를 계산하기 때문에 Time Complexity는 O(N^(1/2)) 루트에 비례라는 자주 보기 힘든 시간 복잡도를 가지게 된다.

 

c. 에라토스테네스의 체

 위의 루트 알고리즘만으로 알고리즘을 풀다가 시간초과에 막히게 되는 경우를 겪게 된 적이 있다. 이 문제에서는 겪지 않지만, 에라토스테네스의 체(Sieve of Eratosthenes)라는 방법을 알게 되었다. 

 그 원리는 다음과 같다.

소수인 수의 배수들을 모두 소수가 아닌 수로 제외시켜버리면서 소수들만 남기는 알고리즘이다. 

Time Complexity는 (NloglogN)이 나온다고 한다.

 

그래서 이 소수 찾기 알고리즘은 에라토스테네스의 체로 풀이하기로 한다.

 

// Code Plus BasicA
// 0x00. Math
// Written by Rylah
// Written Date : 2022.01.14
// https://minteul.tistory.com/309
// https://www.acmicpc.net/source/37537355

// 1978. 소수 찾기
// use Sieve of Eratosthenes
// time Complexity : O(NloglogN)


#include <bits/stdc++.h>
using namespace std;

int Eratos[1003];


int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	for (int i = 2; i < 1003; i++)
		Eratos[i] = i;
	for (int i = 2; i < 1003; i++)
	{
		if (Eratos[i] == 0)
			continue;
		for (int j = i + i; j < 1003; j += i)
			Eratos[j] = 0;

	}


	int testCase;
	cin >> testCase;
	int primeCount = 0;
	while (testCase--) 
	{
		int a;
		cin >> a;
		if (Eratos[a] != 0)
			primeCount++;
	}

	cout << primeCount << '\n';

	return 0;
}