Every prime number is in the form of 6k+1 or 6k-1. In order to check if a number is prime or not we can use the below algorithm. I have seen programs that are written based on these algorithms.
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; } But I don't understand what would have been the problem if we had written code in the following manner:
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; } By this we can reduce the time complexity to O(1) compared to O(root(n)). Please let me know if am heading towards wrong direction.
