(c++)백준 1978번: 소수 찾기

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

1978번: 소수 찾기

[풀이]

에라토스테네스의 체 알고리즘을 이용하여 풀었다.

에라토스테네스의 체 알고리즘은 2부터 판별하고자 하는 가장 큰 수까지 배열에 넣어 소수가 아닌 것들을 체크하는 알고리즘이다.

for문을 돌려 2를 제외한 2로 나누어 떨어지는 모든 수를 체크하고, 3을 제외한 3으로 나누어 떨어지는 모든 수를 체크하고··· 이때 한번 check된 수로는 나누어보지 않아도 된다. 

마지막에 체크되지 않은 수가 소수이다.

 

#include <iostream>
#include <vector>
#include <algorithm>//max
using namespace std;

int N;
int Max = -1;
vector<int>nums;
int check[101] = { 0, };//소수 아니면 -1

//에라토스테네스의 체
void getPrime() {
	for (int i = 2; i < Max; i++) {
		for (int j = 0; j < N; j++) {
			if (nums[j] == i)continue;
			if (nums[j] == 1)check[j] = -1;//1은 소수 아님
			if (nums[j] % i == 0)check[j] = -1;//소수 아님
		}
	}
}

void solution() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int n;
		cin >> n;
		nums.push_back(n);
		Max = max(Max, n);
	}
	getPrime();
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		if (check[i] == 0)
			cnt++;
	}
	cout << cnt << endl;
}

int main() {
	solution();
	return 0;
}