[BOJ] 1978번 소수 찾기 (C++)

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

1978번: 소수 찾기

 

#include <iostream>
using namespace std;

int cnt = 0;

void isPrime(int n) {
	if (n == 1) return;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) return;
	}
	cnt++;
}

int main() {
	int n, num;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> num;
		isPrime(num);
	}
	cout << cnt << endl;

	return 0;
}

소수 = 1과 자기 자신으로만 나누어지는 수 = 약수가 2개인 수

합성수 = 1과 자기 자신을 제외한 다른 약수를 가지고 있는 수

* 1은 소수도 합성수도 아님

 

소수 판정법

합성수 N에서 1을 제외한 가장 작은 약수는 √N 이하이다.

<증명>

합성수 N에서 1을 제외한 가장 작은 약수를 X라 하자.

N/x 또한 1이 아닌 N의 약수이기 때문에 X<=(N/x)

따라서 X^2<=N이므로 X<=√N

-> 2부터 √N까지의 수로 나누어지지 않으면 소수