[백준] 알고리즘 1978번 - 소수 찾기

#include <bits/stdc++.h>
using namespace std; 
bool prime(int number) {
	if (number < 2) {
		return false;
	}
	for (int i = 2; i <= number - 1; i++) {
		if (number % i == 0) {
			return false;
		}
	}
	return true;
}
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, ans = 0;
	cin >> n;
	while (n--) {
		int number;
		cin >> number;
		if (prime(number) == true) {
			ans++;
		}
	}
	cout << ans;
}
 

소수 관련 글

[백준] 알고리즘 수학 - 나머지연산, GCD, LCM, 진법변환, 소수

 

간단하게 소수 관련글을 숙지한 후, 풀 수 있는 문제입니다.

2~n-1 까지의 소수 하나하나를 다 비교해서 풀어봅니다.

다만, 이 방법에는 나중에 시간의 문제가 있어 새로운 유클리드 호제법과 같은 에라토스테네스의 체라는 기법을 이용해보도록 하겠습니다.