[BOJ] 1978번 : 소수 찾기

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int n; 
bool isprime(int a) {
	if (a == 1) return 0; 
	for (int i = 2; i * i <= a; i++) {
		if (a % i == 0) return 0;
	}
	return 1;
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n; 
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		int x; 
		cin >> x; 
		cnt += isprime(x);
	}
	cout << cnt << '\n';
}

소수를 찾기 위해서는 숫자 a가 있을 때, root(a)까지만 검사를 해보면 된다. 그 이유는 어떤 수 a의 1이 아닌 제일 작은 약수를 x라고 하자. 이때, a를 x로 나눈 값, 즉, (a / x)는 x보다 크거나 같은 값이 된다. 따라서, x <= (a / x)가 성립한다. 양변에 x를 곱하고 루트를 씌우면, x <= root(a)가 된다. 따라서, root(a)까지만 검사하면 된다.