[1978번] 소수 찾기

1978번: 소수 찾기

 

www.acmicpc.net

n개의 수가 주어지고, 주어진 수들 중 소수의 개수를 구하는 문제다.

소수는 약수가 1과 자기 자신 밖에 없는 수이다.

그렇다면 소수를 구하려면, 자기 자신 보다 작은 수 들을 나눴을 때,

나눠 지는 것이 없다면 소수라고 할 수 있다.

자신보다 작은 수를 나누다가 나머지가 0

즉, 나눠지는 수가 있으면 합성수라고 체크를 해주고 반복문을 빠져나온다

/*1978번 소수찾기*/
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int arr[101];
int num[1001];//0일 때 소수, -1일 때 합성수 or 1
int prime_cnt;
void eratos(int n) {
	if (n == 1) num[n] = -1;
	if (n > 2) {
		for (int i = 2; i < n; i++) {
			if (n%i == 0) {
				num[n] = -1;
				break;
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)	cin >> arr[i];
	for (int i = 0; i < n; i++) {
		eratos(arr[i]);
		if (num[arr[i]] == 0) prime_cnt++;
	}
	cout << prime_cnt;
}

.