i am looking for the most efficient way to check wetter an integer is prime or not
This is a discussion on looking for efficient algoritm to check wetter an integer is prime or not within the C Programming forums, part of the General Programming Boards category; i am looking for the most efficient way 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
Look here.
Consider this post signed
You even tiny url'ed it.
I've googled it before I came 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?
Last edited by laserlight; 06-28-2010 at 03:56 PM.
C + C++ Compiler: MinGW port of GCC
Version Control System: Bazaar
Look up a C++ Reference and learn How To Ask Questions The Smart Way
Well it is for this problem:
My isPrime algorithm:Code:The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?
my algorithm that searches for the largest factor: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; }
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.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); }
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.
Last edited by bernt; 06-28-2010 at 04:02 PM. Reason: Forgot the link
Consider this post signed
Ah! It looks like you're spending some quality time at projecteuler.net! Good stuff, I'm on problem 49 right now. Good luck!The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
Consider this post signed
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.
Last edited by laserlight; 06-28-2010 at 04:14 PM.
C + C++ Compiler: MinGW port of GCC
Version Control System: Bazaar
Look up a C++ Reference and learn How To Ask Questions The Smart Way
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.
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++; } //divisor is the answer
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.
C + C++ Compiler: MinGW port of GCC
Version Control System: Bazaar
Look up a C++ Reference and learn How To Ask Questions The Smart Way
This can be written a little bit more efficiently
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.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; }
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.
^_^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
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.
1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
3. Get rid of conio.h and other antiquated DOS crap headers.
4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.
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:
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.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; } } }
ITSA Socket Library!