Prime number problem

**Antigloss** · 06-02-2005

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 */

**Thantos** · 06-02-2005

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.

**xErath** · 06-03-2005

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.

**Salem** · 06-03-2005

> 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

**xErath** · 06-03-2005

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

**Antigloss** · 06-03-2005

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?

**Antigloss** · 06-03-2005

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?

**Salem** · 06-03-2005

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

**Thantos** · 06-03-2005

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.

**Antigloss** · 06-03-2005

Thanks all for your kindly help~Especially to Thantos, thanks a million.

**Thantos** · 06-03-2005

/em whisltes
What 9?

**Antigloss** · 06-04-2005

9 ?
Well, the quoted post is the 9th reply of this thread.

Originally Posted by Antigloss

Thanks all for your kindly help~Especially to Thantos, thanks a million.

**laserlight** · 06-04-2005

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.

**Jez** · 06-04-2005

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

Thread: Prime number problem

Thread Tools

Search Thread

Display

Prime number problem

Similar Threads

Prime number algorithm

noob problem with a number generator

prime # query

Random Number problem in number guessing game...

Array of boolean