백준 - 1978번 소수 찾기 (C++)

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

1978번: 소수 찾기

 이번 문제는 숫자가 몇 개 주어졌을 때, 이 수들 중 소수가 몇 개인지를 출력하는 문제이다. 소수는 약수를 자기 자신과 1만을 가지는 수를 의미하기에 하나 하나 직접 검사해볼 수도 있을 것이다. 하지만 이런 식으로 진행한다면 모든 수마다 소수인지 검사해야 하기 때문에 여러모로 낭비가 많을 것이다. 이럴 때, 이용할 수 있는 방법이 에라토스테네스의 체 알고리즘이다. 이 알고리즘은 소수를 판별할 수 있는 알고리즘이다. 이 알고리즘의 대략적인 과정은 다음과 같다. 숫자를 2부터 일정 범위까지 탐색을 진행한다. (1은 소수가 아니다) 만약 탐색 중인 어떤 수 x가 소수가 아니라면, x + x, x + x + x, x + x + x + x ... 등은 소수가 아니므로 이러한 숫자들을 제외시켜 나간다. 이런 식으로 일정 범위 내의 숫자들의 소수 판별이 가능해진다.  이를 이용한 문제 풀이는 다음과 같다. 

1. 1부터 1000까지의 수들을 소수인지 아닌지 미리 구분한다.
2. 각각의 수를 입력 받은 후, 이 수가 소수라면 answer의 값을 1 증가시킨다.

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <memory.h>
#include <deque>
#include <cmath>
#include <stack>
#include <cstring>
#include <typeinfo>
#include <iomanip>
#include <limits.h> 
#pragma warning(disable:4996)

using namespace std;

#define MAX 1001

int N, answer = 0;
int isPrime[MAX];

void CheckPrime()
{
	isPrime[1] = 0;
	
	for (int i = 2; i < MAX; ++i)
		isPrime[i] = i;

	for (int num = 2; num < MAX; ++num)
	{
		if (isPrime[num] != 0)
		{
			for (int nxtNum = num + num; nxtNum < MAX; nxtNum += num)
				isPrime[nxtNum] = 0;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	CheckPrime();

	cin >> N;

	for (int i = 0; i < N; ++i)
	{
		int num;
		cin >> num;

		if (isPrime[num] == num)
		{
			++answer;
		}
	}

	cout << answer << endl;

	return 0;
}