링크 : https://www.acmicpc.net/problem/1978
소수 찾기.
#include <iostream>
#include <cmath>
using namespace std;
bool prime(int n) {
if (n <= 1)
return false;
for (int i = 2; i <= sqrt(n); i++) {
if ((n % i) == 0)
return false;
}
return true;
}
int main() {
int num, elem, total = 0;
cin >> num;
for (int i = 0; i < num; i++) {
cin >> elem;
if (prime(elem))
total++;
}
cout << total << endl;
return 0;
}
소수 찾는 알고리즘을 살펴보자.
if (n <= 1)
return false;
자연수 1보다 큰 수를 기준으로 소수를 판별하므로 1 이하인 수는 return false
를 한다.
for (int i = 2; i <= sqrt(n); i++) {
if ((n % i) == 0)
return false;
}
return true;
2부터 시작하여 sqrt(n)
까지 진행한다. sqrt(n)
까지 진행하는 이유는 다음과 같다. 예를 들어 15의 경우 (1x15), (3x5), (5x3), (15x1)과 같이 거울 상처럼 어느 순간부터 두 숫자의 위치가 바뀐 곳이 등장한다. 이 거울의 위치가 되는 곳이 sqrt(15)
이므로 이 이후를 넘어가면 중복 탐색이다.
나머지 부분은 나머지 연산자를 이용해 (n % i) == 0) == true
가 나오는 경우 소수가 아니므로 return false
해준다. 나눠진다는 말은 자기 자신과 1 외에도 다른 수로 곱해질 수 있다는 뜻이기 때문이다.
길게 쓴 이유는 한번에 통과하지 못했기 때문..