Thread: looking for efficient algoritm to check wetter an integer is prime or not

Look here.

Why do you need to check if an integer is prime? What is the range of these integers? Must you be absolutely certain that the integer is prime, or will you be satisfied knowing that the integer is probably not composite?

You even tiny url'ed it.

By the looks of it there are two solutions. The first is to check if the number is even and then check for divisibility with all the odd numbers from 3 to sqrt(n) including sqrt(n). This would be best done with the modulus (%) operator.

There is an interesting theorem here that seems to work in O(log n ^ (log log log n)) time but I haven't yet made sense of the math; it would be interesting to see an implementation of that.

The final method, assuming sufficient memory, would be to generate a list of primes up to sqrt(n) and test those. The list could be done with a prime sieve or some other prime-generator pretty quickly and stored for later use if you have to test lots of numbers.

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Ah! It looks like you're spending some quality time at projecteuler.net! Good stuff, I'm on problem 49 right now. Good luck!

This is more of a prime factorisation problem than a primality testing problem. I suspect that a suitable yet simple algorithm would be one based on trial division. The idea is that once you have found a prime factor, you repeatedly use integer division to reduce the integer to a smaller one that does not have that prime as a factor. Eventually, the result will be a prime, and that prime will be the largest prime factor of the original integer. You only need to test with primes (or 2 and odd numbers) until the square root of the integer; if you still have not found any prime factors, then that integer must itself be prime.

Yes, you are doing something like what I described, except that it lacks a check to avoid testing beyond the square root. The divisor-- and divisor++ trick can be eliminated with a nested loop.

Originally Posted by boxden

My isPrime algorithm:

Code:

int isPrime(unsigned long long numb)
{
	unsigned long long i, stop = 0;
	for (i = 2; i < numb/2 && !stop; i++) {
		if (numb % i == 0)
			stop = 1;
	}
	if (!stop)
		return 1;
	else
		return 0;
}

This can be written a little bit more efficiently

Code:

int isPrime(unsigned long long numb)
{
	unsigned long long i;
	for (i = 2; i < numb/2; i++) {
		if (numb % i == 0)
			return 0;
	}
        return 1;
}

So you avoid one check. You also help the compiler optimize since it won't have to perform checks at all on every loop, it can just lopp numb/2 times.

You can also think more hardware-wise. If you are using multi-core processors this is generally a "good" function to break into threads. One thread from 2 to numb/4 and the other from numb/4 + 1 to numb/2. Or four threads for a 4-core.

Like Laserlight said this is a factorization problem and from the looks of it, it is one of the Project Euler problems.

There are several approaches to this problem but one of the best I have seen deals with simulating a generalized Eratosthenes' seeve (is that the spelling?). Think about how you would do that for very large numbers. And you can generally skip a ton of comparisons that you would test for using a loop from 2 to the upper limit.

Actually, the test for primality is unnecessary, since multiples of previous factors will always fail subsequent divisibility tests. I'd do it like this, personally:

Code:

template < typename Unsigned, typename Iterator >
void factor( Unsigned val, Iterator out )
{
	static Unsigned const
		lwb = 2;
	if( val >= lwb )
	{
		bool
			fnd = false;	
		for( Unsigned cmp = lwb, rot = sqrt( val ); cmp <= rot; ++cmp )
		{		
			while( !( val % cmp ) )
			{
				fnd = true;
				*out++ = cmp;
				val /= cmp;			
			}
		}
		if( !fnd )
			*out++ = val;
	}
}

// Example:

#include <cmath>
#include <iostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>

int main( int argc, char* argv[ ] )
{
	using namespace
		std;
	while( *( ++argv ) )
	{
		unsigned 
			val;
		stringstream
			cvt;
		cvt << *argv;
		if( cvt >> val )
		{
			cout << "(" << val << ") : ";
			vector< unsigned >
				fac;
			factor( val, back_inserter( fac ) );
			if( fac.empty( ) )
				cout << "domain is invalid" << endl;
			else if( fac.size( ) == 1 )
				cout << "number is prime" << endl;
			else
				cout << "number is composite" << endl;
			copy( fac.begin( ), fac.end( ), ostream_iterator< unsigned >( cout, "\n" ) );
			cout << endl;
		}
	}	
}

You could make it much more effecient by following Laserlight's suggestion to skip even numbers. Of course, the logic is a little more tricky there. I'll just leave that as an exercise for the reader, though.