Ankit Gupta

HCI & Health Informatics Researcher | Visual Analyst | Full Stack Developer

What is the fastest way to find if a number is prime?

Quoting wikipedia,

prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

So, at times you might find a need to check if a number is prime. And if the numbers to be checked for primality, you might need the fastest implementation. In this post, I am sharing the implementation as suggested by the algorithm here.

boolean isPrime(long number) {
	if (number == 2) {
	    return true; // 2 is a prime
	}

	// if the number is even
	if (number % 2 == 0 || number < 1) {
	    return false; // not a prime.
	}

	// a number would be prime if it is not divisible by a number less than or equal to its square root.
	double root = Math.sqrt(number);

	//we start the loop from 3 (2 is already checked above)
	//Additionally, we will increment i by 2 as checking for even divisor is not required at this point.
	for (double i = 3; i <= root; i = i + 2) {
	    if (number % i == 0) {
		return false;
	    }
	}

	return true;
}

Comments

NEWS
  • 19 March 2018
    I got a full-paper accepted at Pervasive Health 2018
  • 15 March 2018
    Qualified for SFU 2018 3MT finals