Elysian Shadows

Posted: **Sun Jun 19, 2011 11:57 pm**

This is a quick and easy prime number test because I'm seriously sick of searching all over the web for a faster way. So I wrote three and decided that the one with the least lines of code actually looks like it works better.

Code: Select all

bool isPrime(long n)
{
	if (n < 2) return false;
	if (n < 4) return true;
	if (n % 2 == 0) return false; // if number modulo 2 returns 0 then it's even, and not prime
	const unsigned int i = sqrt((double)n) + 1;
	for (unsigned int j = 3; j <= i; j += 2)
	{
		if (n % j == 0)
			return false;
	}
	return true;
}

Oh and you must #include <math.h>
For more information look up Sieve of Eratosthenes and AKS. The codes based on both.

Posted: **Sat Jun 25, 2011 2:21 pm**

sqrt() is slow. Especially math.h's version.

There might be a builtin for finding next power of 2, but I forgot it.

Code: Select all

bool isPrime2(unsigned int n) {
  if (n % 2 == 0) return false;
  unsigned int nl = n;
  nl |= (nl >> 1);
  nl |= (nl >> 2);
  nl |= (nl >> 4);
  nl |= (nl >> 8);
  nl |= (nl >> 16);
  nl += 1;
  nl >>= ((__builtin_ctz(nl))>>1);
  for(unsigned int i = 3; i < nl; i += 2) {
    if(n % i == 0)
      return false;
  }
  return true;
}

Elysian Shadows

Quick and easy prime number test because...

Quick and easy prime number test because...

Re: Quick and easy prime number test because...