Проверка приоритета

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; 
} 

Но я не понимаю, что было бы проблемой, если бы мы написали код следующим образом:

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 (1), по сравнению к O (корень (n)). Пожалуйста, дайте мне знать, если я направлюсь в неправильном направлении.

Answer 1

Правильно сказать, что каждое простое (кроме 2 и 3) имеет остаток от 1 или 5 при делении на 6 (см. this page для более глубокого объяснения). Однако противоположное утверждение неверно. Не каждое число, имеющее остаток от 1 или 5, если делится на 6, является простым.

Возьмите 35, например. Он имеет остаток от 5 при делении на 6, однако он не является простым (35 = 5 х 7).