1 Replies - 1949 Views - Last Post: 09 October 2012 - 08:12 PM

#1 RetardedGenius   User is offline

  • >>──(Knee)──►
  • member icon

Reputation: 127
  • View blog
  • Posts: 555
  • Joined: 30-October 10

Deterministic Primality Test

Posted 19 May 2011 - 08:35 AM

Description: This function takes an integer, as an argument, and returns true if it is a prime number, false if it is composite. Please feel free to modify, use it as you see fit. ;)This function tests a number for primality. It is designed to be small and clear to understand, but also efficient for both memory and processor usage. The algorithm used works on the observation that all primes, > 3, of the form 6k 1.
inline bool IsPrime(int n)
{
	if (n == 2 || n == 3)
		return true;
	if (n < 2 || n % 2 == 0 || n % 3 == 0)
		return false;
	for (int k = 5; k*k <= n; k += 6)
		if (n % k == 0 || n % (k + 2) == 0)
			return false;
	return true;
}


Is This A Good Question/Topic? 0
  • +

Replies To: Deterministic Primality Test

#2 scurveedog   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 23-September 12

Re: Deterministic Primality Test

Posted 09 October 2012 - 08:12 PM

Fantastic prime algorithm, very elegant and a major speed increase over my orig. algorithm
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1