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

1. ## looking for efficient algoritm to check wetter an integer is prime or not

i am looking for the most efficient way to check wetter an integer is prime or not

2. Look here.

3. You even tiny url'ed it.
I've googled it before I came here.

4. 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?

5. Well it is for this problem:

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

What is the largest prime factor of the number 600851475143 ?```
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;
}```
my algorithm that searches for the largest factor:
Code:
```void PrimeFactors(unsigned long long numb)
{
unsigned long long i = 2, highfac;
while (i < numb / 2) {
if (numb % i == 0 && isPrime(i))
highfac = i;
printf("%llui\n", i);
i++;
}
printf("%lli\n", highfac);
}```
Could be that the inefficience is in the second one though anyway it's taking way to long to get there, so my algorithms need to be more efficient.

6. 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.

7. 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!

8. 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.

9. Lol, I replaced numb / 2 with sqrt(numb) and it found a solution within a second
I should have thought about that... Thank you for all the help.
And nice work, bernt. I just started today, this was problem 3.

10. For those interested, this is very clean and short
Code:
```__int64 number = 317584931803;
int divisor = 2;
while (number > 1) {
if (0 == (number % divisor)) {
number /= divisor;
divisor--;
}
divisor++;
}

11. 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.

12. 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.

13. i am looking for the most efficient way to check wetter an integer is prime or not
^_^

My computers have been working on this problem for months. Let us all know if you find one.

Soma

14. 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.

15. 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.