숫자가 소수인지 확인하는 데 사용되는 알고리즘의 장단점은 무엇입니까?

Question

내 코드는 다음과 같습니다. 나는 이것이 속도와 기억면에서 다른 알고리즘과 어떻게 비교되는지를 우선적으로 알고 싶다.

Answer 1

우선, 귀하의 알고리즘은 선형 시간 O (n)을 취합니다. 최대 sqrt(n) (i * i <= n)까지의 숫자 만 확인하면 속도를 대폭 향상시킬 수 있습니다. 그 말은, 만약 당신이 소수 ~ 크기의 k 개의 번호를 확인하고 싶다면 O(k sqrt (n))으로 끝날 것입니다. 여전히 나쁘다. 이 경우

, 당신은 n까지 번호를 O(n log log n)에서 구현 될 수있다 체 ( Atkins 또는 Eratosthenes)를 구축한다. 이 방법으로 모든 후속 테스트를 O (1)에서 수행 할 수 있습니다.

Answer 2

짝수 후보 (2 제외) 중 어느 것도 소수이기 때문에 홀수와 2를 스테핑해야합니다. 다른 이유로 루프는 i <= input/3에서 종료해야합니다. 나는 당신의 실행 속도를 여섯 배로 늘 렸습니다.

bool isPrime(int input){ 
    int endval = input/3; 
    if (input <= 2) 
     return true; 
    if ((input & 1) == 0) 
     return false; 
    for(int i = 3; i <= endval; i+=2) 
     if(input%i == 0) 
      return false; 
    return true; 
} 

Answer 3

다음과 같은 방법으로 시도해 볼 수 있습니다 (모든 가능한 경우를 선택했는지 확신 할 수 없음). 잠재적 인 오버플로 문제를 피하려면 (i * i) < = input 대신 i < = (input/i)이 사용됩니다.

bool isPrime(int input){ 
int i; 
    if(input%2 == 0) 
     return false; 
    for(i = 3; i <= (input/i); i += 2) 
     if(input%i == 0) 
      return false; 
    return true; 
}