Algoritem/Problem solving
소수 판별법
신우섭
2020. 5. 25. 16:14
핵심
소수는 1과 자기자신으로 나누어 떨어지는 수
소수를 판별하는 가장 간단한 방법은
1과 자기자신을 제외한 2 ~ n-1 까지 수로 나누어서 떨어지는지 확인하는 것 이다.
이것은 O(n)의 시간 복잡도를 갖으며 이 방법을 개선한 방법으로
1과 n을 제외한 n의 약수가 존재할 때 가장 작은 약수 a는 a <= \sqrt n 이라는 명제를 가지고
O(logN)의 시간 복잡도를 갖을 수 있도록 한다.
void Funtion(int n)
{
if (n <= 2) return false;
for (int i = 2; i * i <= n; i++)
{
if (n % i == 0) return false;
}
return true;
}