Prime number problem

This is a discussion on Prime number problem within the C Programming forums, part of the General Programming Boards category; I wrote a program to accept an even integer, then divide the integer into two prime numbers' sum and display ...

  1. #1
    C/C++Newbie Antigloss's Avatar
    Join Date
    May 2005
    Posts
    212

    Prime number problem

    I wrote a program to accept an even integer, then divide the integer into two prime numbers' sum and display the result.
    But the function 'isprime' I wrote to judge if a number is prime number or not is not so efficient. Could you please tell me some efficient algorithm?
    Thanks in advance.
    Code:
    #include <stdio.h>
    #include <math.h>
    
    int isprime( long );/* return 1 if the is prime number, otherwise return 0  */
    int input( long * );/* return 1 if the input is legal, otherwise return 0 */
    
    int main()
    {
    	long even = 0,
    	     i    = 0;
    
    	while ( 1 ) {
    		fputs( "Input an even not less than 4: ", stdout );
    		if ( input( &even ) ) {
    			if ( even < 4 || even % 2 ) {
    				;
    			} else { /* if even is not an odd number and not less than 4, exit the loop */
    				break;
    			}
    		}
    		puts( "Invalid!" );
    	}
    
    	for ( i = 2; i <= even/2; i++ ) {
    		if ( isprime( i ) && isprime( even - i ) ) {/* if i and (even-i) are prime numbers */
    			printf( "%ld = %ld + %ld\n", even, i, even - i );/* display the result */
    		}
    	}
    
    	return 0;
    }
    
    /* definition of isprime() starts here */
    int isprime( long arg )
    {
    	int  return_val = 1;
    	long bound = ( long ) sqrt ( arg );
    	long div;
    	/* arg is prime number for sure if can't find any divisor
    	 * from 2 to bound(arg's square root) to divide arg exactly. */
    	for( div = 2; div <= bound; div++ ){
    		if ( !( arg % div ) ) { /* if find a divisor to divide arg, return 0 */
    			return_val = 0;
    			break;
    		}
    	}
    
    	return return_val;
    }
    /* definition of isprime() ends here */
    
    /* definition of input() starts here */
    int input( long *arg )
    {
    	int ch;
    	int return_val = 0; /* used as a return value */
    
    	if ( scanf( "%ld", arg ) == 1 ) { /* assign return_val with true if integer is inputed */
    		return_val = 1;
    	}
    	while ( ( ch = getchar() ) != '\n' && ch != EOF ) {/* eliminate garbage in stdin */
    		;
    	}
    
    	return return_val;
    }
    /* definition of input() ends here */
    Last edited by Antigloss; 06-03-2005 at 12:27 AM.

  2. #2
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    The most obvious:
    Code:
    for( div = 2; div <= bound; div++ )
    If a number can't be divided by two it can't be divided by 4, 6, 8, 10, etc so there is no need to check them
    Code:
    if ( arg % 2 == 0 )
      return_val = 0;
    else
      for( div = 3; div <= bound; div+=2 )
    What is the range of numbers you are using?

    One easy way is to preload all the prime numbers up to the sqrt of the largest possible value into an array and then cycle through that array checking to see if the number is divisible.

  3. #3
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    The square root stuff is well thought
    Thantos advice to.

    If a number is mutiple of three, the nine's proof (sum all digit recursivly until you get only one, decimal) will be 0,3,6. But probably this one isn't that good.
    Last edited by xErath; 06-03-2005 at 01:27 AM.

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,761
    > for( div = 2; div <= bound; div++ )
    This should be
    for( div = 2; div <= bound; div = next_prime(div) )

    If you were running the sieve manually (or drew it out on paper to actually see it working), you would be striking out multiples of 2,3,5,7,11,13 etc
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    Quote Originally Posted by Salem
    > for( div = 2; div <= bound; div++ )
    This should be
    for( div = 2; div <= bound; div = next_prime(div) )

    If you were running the sieve manually (or drew it out on paper to actually see it working), you would be striking out multiples of 2,3,5,7,11,13 etc
    but that implies calculating the next prime number, which is what he's trying to do

  6. #6
    C/C++Newbie Antigloss's Avatar
    Join Date
    May 2005
    Posts
    212
    Quote Originally Posted by Thantos
    What is the range of numbers you are using?

    One easy way is to preload all the prime numbers up to the sqrt of the largest possible value into an array and then cycle through that array checking to see if the number is divisible.
    How to preload the prime numbers? Manual preload?

  7. #7
    C/C++Newbie Antigloss's Avatar
    Join Date
    May 2005
    Posts
    212
    Quote Originally Posted by Salem
    > for( div = 2; div <= bound; div++ )
    This should be
    for( div = 2; div <= bound; div = next_prime(div) )

    If you were running the sieve manually (or drew it out on paper to actually see it working), you would be striking out multiples of 2,3,5,7,11,13 etc
    Is next_prime() in the standard library?

  8. #8
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,761
    > which is what he's trying to do
    No, he's trying to verify that a given number is prime, not find a list of all prime numbers.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  9. #9
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Quote Originally Posted by Antigloss
    How to preload the prime numbers? Manual preload?
    You can manually preload all or some (and then calculate the rest).

    The reasoning for this is because when checking to see if a number is prime you only need to check it against other prime numbers. So lets say my range of numbers was 2 - 100. I would preload the array as such:

    Code:
    int knowPrimes[] = { 2, 3, 5, 7, 11 };
    Why is 11 in there? For safety since 7 * 7 < 100
    So now I can do a loop like this:
    Code:
    int i;
    for( i=0; knowPrimes[i] * knowPrimes[i] <= n; i++)
      if ( n % knowPrimes[i] == 0 )
      {
        return_val = 0;
        break;
      }
    If you can't manually preload some of the primes then right a routine that will generate a list of them, store it as a pointer and pass this list of know primes.

  10. #10
    C/C++Newbie Antigloss's Avatar
    Join Date
    May 2005
    Posts
    212
    Thanks all for your kindly help~Especially to Thantos, thanks a million.
    Last edited by Antigloss; 06-03-2005 at 07:44 PM.

  11. #11
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    /em whisltes
    What 9?

  12. #12
    C/C++Newbie Antigloss's Avatar
    Join Date
    May 2005
    Posts
    212
    9 ?
    Well, the quoted post is the 9th reply of this thread.
    Quote Originally Posted by Antigloss
    Thanks all for your kindly help~Especially to Thantos, thanks a million.

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,157
    Why is 11 in there? For safety since 7 * 7 < 100
    hmm... but there is no composite in the range of (1, 121) that does not have a factor that is either 2, 3, 5 or 7.

    I'm not too clear on the maths, but it seems to me that for primality testing numbers less than the square of the nth prime by trial division, one only need to test with all primes up to the (n-1)th prime.
    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

  14. #14
    Jez
    Jez is offline
    The C-er
    Join Date
    Mar 2004
    Posts
    192
    @antigloss
    Code:
    for( div = 2; div <= bound; div++ ){
    here's a more efficient way
    Code:
    for( div = 5,increment=2; div <= bound; div+=increment, increment=6-increment ){
    this loop skips attempts to divide by multiples of 3 too, i.e. it runs
    5,7,11,13,17,19,23,25.....

    of course you need to check for divisibility by 2 and 3 first. The idea can be extended to miss other multiples, but it soon gets unwieldy.

    The "sieve" that Salem refers to is the Sieve of Eratosthenes. I did a quick search on Google, there's lots of stuff about this.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Prime number algorithm
    By Akkernight in forum C Programming
    Replies: 9
    Last Post: 04-19-2009, 02:50 PM
  2. noob problem with a number generator
    By Amoreldor in forum C Programming
    Replies: 14
    Last Post: 03-10-2005, 10:39 AM
  3. prime # query
    By alokin in forum C Programming
    Replies: 8
    Last Post: 09-04-2002, 12:50 PM
  4. Random Number problem in number guessing game...
    By -leech- in forum Windows Programming
    Replies: 8
    Last Post: 01-15-2002, 05:00 PM
  5. Array of boolean
    By DMaxJ in forum C++ Programming
    Replies: 11
    Last Post: 10-26-2001, 12:45 AM

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