-
효율적인 소수 판별법(√ n까지만 나눠보면 되는 이유)카테고리 없음 2021. 9. 13. 23:01
소수
소수란 1과 자기 자신만으로 나누어 떨어지는 1보다 큰 양의 정수를 말한다.즉 1과 자기 자신이 아닌 수(2~n)로 나눠지면 소수이고, 나눠지지 않으면 소수가 아니다.
이를 코드로 구현해보자(C++)
12345678910111213int IsPrime(int num){if (num < 2)return false;for (int i = 2; i < num; ++i){if (num % i == 0)return false;}return true;}cs 하지만 이는 너무 비효율적이다.
사실 √ n까지만 확인을 해보면 된다.
구체적인 예를 보자.
100이라는 수가 소수인지 아닌지 판별해보도록 하겠다.
100의 약수는 100, 50, 25, 20, 10, 5, 4, 2, 1이다
이 약수들의 곱으로 100이라는 수를 표현해보면 아래와 같다.
같은 수의 곱으로 이루어진 구간을 넘어가면 수의 위치만 바뀌었을 뿐 이미 나왔던 곱셈 패턴이 반복되는 것을 알 수 있다.
즉 100이 4로 나눠진다면 25로 나눠볼 필요가 없다는 것을 의미하고, 5로 나눠진다면 20로 나눠볼 필요가 없다는 것을 의미한다.
구현(C++)
12345678910111213int IsPrime(int num){if (num < 2)return false;for (int i = 2; i*i <= num; ++i) // i <= sqrt(num)과 같다{if (num % i == 0)return false;}return true;}cs
