isPrime function, which way is better?

[Mathhead200]

I was thinking about how we test the "prime-ness" of a number, and it occurred to me that as I'm checking to see if a number is divisible by the numbers less then it (greater then 1), I ignore checking other prime numbers. (Also you only need to check up to half way.) Like so:

Is 23 prime?

23 % 2 != 0
23 % 3 != 0
ignore 4 because 4 == 2*2
23 % 5 != 0
ignore 6
23 % 7 != 0
ignore 8, 9, 10
23 % 11 != 0
floor( 23 / 2 ) == 11 so stop here.

23 is prime!

This lead me to believe that maybe I could implement an isPrime function with better performance using this technique.

//verson A, without the technique
bool isPrime(int n) {
	if( n <= 1 )
		return false;
	int half = n / 2;
	for( int i = 2; i <= half; i++ )
		if( n % i == 0 )
			return false;
	return true;
}

//verson B, with the technique
bool isPrime(int n) {
	if( n <= 1 )
		return false;
	int half = n / 2;
	for( int i = 2; i <= half; i++ )
		//use a recursive call to check for prime-ness first
		if( isPrime(i) && n % i == 0 )
			return false;
	return true;
}

However I then though, well I only use this shortcut because I can remember which (lower) numbers are prime while on a computer recursive calls can take up a lot of memory, and it's probably harder for me to determine if
n % i == 0 then it is for a computer. So which method is better?

[blackcoder41]

I think version B is better when dealing with higher value of primes. Also all primes are even except 2 so maybe you can +=2 in your for loop.

Hope that helps.

[edit]
Fixed sentence.

[ne555]

You could store the results of the recursive calls to ease the computation. (dynamic programming)
Also just need to check till sqrt(n)

[Mathhead200]

blackcoder41

...all primes are [not] even except 2...

But the same goes for multiples of 3, 5, 7, 11, ..., p_n hence the recursive isPrime call.
Is there an easier (faster) way to jump numbers then to check if it's prime (like the i += 2 idea?)

Nice catch ne555, I didn't think about that...

[blackcoder41]

Oh my bad, thanks for your correction Mathhead200. Must be a brain malfunction.

[imi]

If you only need the fist couple of say.. thousand primes, its probably fastest to just pre-calculate them, hold them in a big array and do a binary search. (If your test-input is random, do a quick %2, %3, %5... - check before the lookup with the number of checks approximately equal to the logarithm of the size of your pre-calculated buffer).

If you want to test for very large numbers (e.g. used in cryptography applications) and you are really concerned about speed, take a look at common math libraries and their bigint - classes (or equivalents). There are usually "ProbablyPrime()" - functions that are much much much ... much faster for very large prime numbers drawn out of random numbers1), but which may fail in a neglectable2) number of cases

1) Some of the algorithms won't work if the number under test is not random, but may come from "mallicious" source. Beware of this, especially in cryptographic applications!

2) "neglectable" as in "a much smaller probability as that a random bit in your memory suddenly flips because of RAM-malfunction and you get a wrong result in your other algorithm too" ;-)

[Mathhead200]

imi

There are usually "ProbablyPrime()" - functions

Actually I'm taking a number theory course, and we have talked a bit about such functions.
Do you have any links I should look at? If not I'll just google it.

...As to not get away from the topic, I was strictly looking at how to optimized the first function above (moreover, will the recursive call optimize the function in any case); and I though about storing primes in an array, however I don't have any preconditions about the size of the input value; and also, would construction of the array within the function (to avoid holding onto memory) be faster then not using one?

[jsmith]

B will be orders of magnitude slower than A.

The point of the array of primes is to compute them only once. Making it local (non-static) to the function defeats that purpose. It is still better (or at least not worse) to store the first N primes in an array, even if the size of the input is unbounded.