정공법으로 소수 판별 시 더 빠른 방법은?
앞 포스팅에서도 짧게 언급했는데, 소수 여부를 판별하는 가장 빠른 방법은 에라토스테네스의 체다. 수의 범위가 정해져있다면 그 범위까지의 소수를 모두 식별하는데 이것보다 빠른 방법은 없다. 하지만, 반대로 이 방식은 임의의 한 수가 소수인지 식별할 때는 오히려 느린 편이다. 일일이 숫자를 나눠서 확인하는 경우 더 빠른 방법이 어느쪽인지 테스트해봤다. 테스트 환경은 그냥 개인용 PC(AMD Ryzen 5 3600X)인데, 다른 환경이라고 큰 차이는 없을 듯. 0. 에라토스테네스의 체 그냥 지나치긴 뭐해서 일단은 간단히 구현해봤다. bool IsPrime_0(unsigned num) { switch (num) { case 0: case 1: case 9: return false; case 2: case 3: ..