소수 검사

Question

모든 소수는 6k + 1 또는 6k-1 형태입니다. 숫자가 소수인지 아닌지를 확인하기 위해 아래의 알고리즘을 사용할 수 있습니다. 이 알고리즘을 기반으로 작성된 프로그램을 보았습니다.

public boolean isPrime(int n) 
{ 

    if (n <= 1) return false; 
    if (n <= 3) return true; 

    if (n%2 == 0 || n%3 == 0) return false; 

    for (int i=5; i*i<=n; i=i+6) 
     if (n%i == 0 || n%(i+2) == 0) 
      return false; 

    return true; 
} 

하지만 우리는 다음과 같은 방식으로 코드를 작성했다면 문제했을 이해하지 않습니다 : (1)에 비해 우리는 O의 시간 복잡도를 줄일 수 있습니다 이것에 의하여

public boolean isPrime(int number){ 
     boolean primeFlag = false; 
     if(number == 0 || number ==1){ 
      return primeFlag; 
     } 
     if(number == 2 || number == 3){ 
      primeFlag = true; 
     } 
     if((number+1)%6 == 0){ 
      primeFlag = true; 
     } 
     if((number-1)%6 == 0){ 
      primeFlag = true; 
     } 
     return primeFlag; 
    } 

~ O (루트 (n)). 잘못된 방향으로 향하고 있는지 알려주세요.

Answer 1

모든 소수 (2와 3 제외)는 6으로 나눌 때 1 또는 5의 나머지를가집니다 (자세한 설명은 this page 참조). 그러나 그 반대는 사실이 아닙니다. 6으로 나눌 때 1 또는 5의 나머지를 갖는 모든 숫자가 소수가되는 것은 아닙니다.

예를 들어 35를 사용하십시오. 6으로 나눌 때 나머지는 5이지만 소수가 아닙니다 (35 = 5 x 7).