Prime number algorithm

This is a discussion on Prime number algorithm within the C Programming forums, part of the General Programming Boards category; Hello. Could anyone help me with a prime number algorithm? I'm not asking for direct code, but pesudo would be ...

  1. #1
    Hail to the king, baby. Akkernight's Avatar
    Join Date
    Oct 2008
    Location
    Faroe Islands
    Posts
    717

    Prime number algorithm

    Hello.

    Could anyone help me with a prime number algorithm?
    I'm not asking for direct code, but pesudo would be nice...
    This is what I currently got

    Code:
    int isPrime(const int number){
    
    	int i; // variable for the loop
    
    	double d; // variable to store the division and hold the decimals
    	int x;	// variable to help check if a division had decimals
    
    	if( number <= 1) return 0; // if 'number' is equal to 1, it's not a prime number "The number 1 is by definition not a prime number" - Wikipedia
    
    	for(i = 2; i != number; ++i){ // 'i' must start at 2
    
    		d = number/i;
    		x = d;	// and integer cannot hold decimals
    
    		if(d == x) return 0;	// if d and x are equal, then it can't be a prime
    	}
    
    	return 1;
    }
    Thanks in advance!
    Currently research OpenGL

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Here's a handy speed up for your algorithm:

    A number is prime if it can not be evenly divided by any number UP TO (including), the square root of that number.

    Code:
    int isPrime(const int number){
    
    	int i; // variable for the loop
    
    	double d; // variable to store the division and hold the decimals
    	int x;	// variable to help check if a division had decimals
    
    	if( number <= 1) return 0; // if 'number' is equal to 1, it's not a prime number "The number 1 is by definition not a prime number" - Wikipedia
    
    	for(i = 2; i != number; ++i){ // 'i' must start at 2
    
    		d = number/i;
    		x = d;	// and integer cannot hold decimals
    
    		if(d == x) return 0;	// if d and x are equal, then it can't be a prime
    	}
    
    	return 1;
    }
    Instead of working with a double (which is sure to slow things down), what about using integers, with the modulo operator: %?

    if(number modulo testNumber equals zero) kind of stuff.
    Last edited by Adak; 04-19-2009 at 09:21 AM.

  3. #3
    Hail to the king, baby. Akkernight's Avatar
    Join Date
    Oct 2008
    Location
    Faroe Islands
    Posts
    717
    hmm... that's actually brilliant
    Thanks!
    Currently research OpenGL

  4. #4
    Hail to the king, baby. Akkernight's Avatar
    Join Date
    Oct 2008
    Location
    Faroe Islands
    Posts
    717
    Just to share my snippets I'm working on! (and done with now xP)

    Code:
    // Problem 5 - Write a function that checks if the passed number is a prime number
    
    int isPrime(const int number){
    
    	int i; // variable for the loop
    
    	if( number <= 1) return 0; // if 'number' is equal to 1, it's not a prime number "The number 1 is by definition not a prime number" - Wikipedia
    
    	for(i = 2; i != number; ++i){ // 'i' must start at 2
    
    		if(number % i == 0) return 0;	// if there arem't any 'left overs' after the divide, then it can't be a prime
    	}
    
    	return 1;
    }
    
    
    // Problem 6 - Write a function that checks if the passed number is a 'perfect' number
    
    int isPerfect(const int number){
    
    	int sum = 0;	// variable that will hold all the dividors and then we check if it adds up to 'number'
    	int i;			// variable for the loop
    
    	for(i = 2; i <= number; ++i){
    
    		sum += number/i;
    
    		if(number/i == 1) break;
    	}
    
    	if(sum == number) return 1;
    	else return 0;
    
    }
    Currently research OpenGL

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    What about outside the loop, getting the square root of the number being tested, in an integer form, though.

    sqr_root = the square root of the number being tested for primeness.
    sqr_root++; because we're using integers
    then

    for( i = 2; i < sqr_root; ++i) //which oddly, is the same as i++, inside a for loop - try it
    //etc.

    This will save you *lots* of processing - more as the numbers increase, of course.

  6. #6
    Hail to the king, baby. Akkernight's Avatar
    Join Date
    Oct 2008
    Location
    Faroe Islands
    Posts
    717
    I don't get it... What would the square root be doing/helping with?
    Currently research OpenGL

  7. #7
    Making mistakes
    Join Date
    Dec 2008
    Posts
    476
    Just store all primes you've calculated in a list (resize it when neccessary), starting with 2. For each new number, if it can't be diviedd by any of these, it's also a prime. I don't know if it's more efficient than sqrt (which is very CPU-intensive), but it's easier.

  8. #8
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by Akkernight View Post
    I don't get it... What would the square root be doing/helping with?
    It's a rule in mathematics. If any number has no number that evenly multiplies into it, which is less than or equal to, it's square root, then it's a prime number.

    Say you wanted to test the number 257. Math tells us that if 257 can't be divided by any number less or equal to it's square root, then it's a prime number:

    So you only need to test from 2 to 17, instead of 2 through 256.

    Brafil's idea of storing the prime numbers you've found so far, is also an excellent one. A bit more bookkeeping, but a *big* time saver.

    Putting both of these idea's together would be a nice one-two punch for finding primes.

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,256
    You can read the entries for the Prime Number Generator contest for more ideas.
    EDIT:
    Quote Originally Posted by Adak
    It's a rule in mathematics. If any number has no number that evenly multiplies into it, which is less than or equal to, it's square root, then it's a prime number.

    Say you wanted to test the number 257. Math tells us that if 257 can't be divided by any number less or equal to it's square root, then it's a prime number:
    Maybe it would be easier to understand if we approach it from the point of view of the prime factors of a composite rather than stating it as a rule for primes.

    Consider an arbitrary integer n > 1 such that n is a composite number. It follows that n has a prime factor p, and another factor q such that p * q = n. If p is equal to q, then p is the positive square root of n, by definition of square root. Consequently, if p is less than q, then p is less than the square root of n. But if p is greater than q, then consider that q must either be prime or a product of primes. If q is not prime, then it must be a product of primes, each of which is less than the square root of n. Hence n must have a prime factor less than or equal to its square root. Thus, we only need to test with primes less than or equal to the square root of the candidate integer for primality testing by trial division.
    Last edited by laserlight; 04-19-2009 at 01:08 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

  10. #10
    Registered User
    Join Date
    Apr 2009
    Posts
    16
    2 the number is even
    924 is divisible by 2 since
    924 is even.

    3
    The sum of the digits is divisible by three
    924 is divisible by 3 since the sum
    of the digits 9 + 2 + 4 = 15 and 15
    is divisible by 3

    4
    the numbers formed by the last two digits of the
    number is didisible by 4
    924 is divisible by 4 cause 24 is divisible by 4
    5
    the number ends in 0 or 5
    265 is divisible by 5 since the number ends with 0 or 5
    6
    the number is divisible by both 2 and 3
    924 is divisible by 6 since since it is since it tested true
    by both 2 and 3
    8
    the number formed by the last digits of the number
    is divisible by 8
    5824 is divisible by 8 since the last three digits
    824 is divisible by 8
    9
    the sum of the digits of the number
    is divisible by 9
    837 is divisible by 9 since the sum of the digits
    8 + 3 + 7= 18 and is divisible by nine.

    If any of these test true then the number is not prime.



    Personaly I'd use a count to keep tract of the numbers divisible If the count went above 1 then reset count and start at the next number. if it finds a prime number print it out
    You only have to check with prime numbers and you only have to check up to the sqt() of the number you want to know is prime. Also Eventhought its cheating I would count by two on the numbers to be tested.
    Last edited by strictlyC; 04-19-2009 at 02:57 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Calculating prime factor of a huge number.
    By Bakster in forum C Programming
    Replies: 15
    Last Post: 02-20-2009, 12:06 PM
  2. how do i calculate prime number
    By pimp in forum C Programming
    Replies: 50
    Last Post: 01-12-2008, 10:25 PM
  3. Replies: 6
    Last Post: 11-04-2002, 05:11 PM
  4. prime # query
    By alokin in forum C Programming
    Replies: 8
    Last Post: 09-04-2002, 12:50 PM
  5. Homework help
    By Jigsaw in forum C++ Programming
    Replies: 2
    Last Post: 03-06-2002, 05:56 PM

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