looking for efficient algoritm 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...

  1. #1
    Registered User
    Join Date
    Mar 2010
    Posts
    44

    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. #2
    Just a pushpin. bernt's Avatar
    Join Date
    May 2009
    Posts
    426
    Look here.
    Consider this post signed

  3. #3
    Registered User
    Join Date
    Mar 2010
    Posts
    44
    You even tiny url'ed it.
    I've googled it before I came here.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,973
    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

  5. #5
    Registered User
    Join Date
    Mar 2010
    Posts
    44
    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. #6
    Just a pushpin. bernt's Avatar
    Join Date
    May 2009
    Posts
    426
    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

  7. #7
    Just a pushpin. bernt's Avatar
    Join Date
    May 2009
    Posts
    426
    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!
    Consider this post signed

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,973
    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

  9. #9
    Registered User
    Join Date
    Mar 2010
    Posts
    44
    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. #10
    Registered User
    Join Date
    Mar 2010
    Posts
    44
    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

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,973
    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

  12. #12
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    Quote Originally Posted by boxden View Post
    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. #13
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    3,803
    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. #14
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    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.

  15. #15
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,600
    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.
    Code:
    if( numeric_limits< byte >::digits != bits_per_byte )
        error( "program requires bits_per_byte-bit bytes" );
    24bbs.cpp

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. help assignment due tomorrow
    By wildiv in forum C Programming
    Replies: 6
    Last Post: 01-27-2010, 07:38 PM
  2. Link List math
    By t014y in forum C Programming
    Replies: 17
    Last Post: 02-20-2009, 05:55 PM
  3. Operator Overloading (Bug, or error in code?)
    By QuietWhistler in forum C++ Programming
    Replies: 2
    Last Post: 01-25-2006, 07:38 AM
  4. how to check if a argument passed is integer
    By powinda in forum C Programming
    Replies: 7
    Last Post: 03-07-2004, 04:26 PM
  5. How is to check prime number?
    By Unregistered in forum C Programming
    Replies: 7
    Last Post: 10-04-2001, 11:36 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21