소수 찾기 / 소수 구하기 _ 백준 1978,1929

1978번, 1929번 문제는 소수와 관련된 문제이다. 어떤 수 N이 소수가 아니라면, N = a * b 라고 표현할 수 있는데, 이떄 a와 b의 차이가 가장 적은 경우는 √n 이다. 그러므로, 검사를 n까지만 해서, 소수를 찾을 수 있다. 이러한 소수의 특징을 이용하면, 아래와 같은 함수를 만들 수 있다. (true = 소수 false = 소수아님) bool prime(int n) { if (n < 2) return false; for (int i = 2; i * i