1. ## 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?
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 */```

2. 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. The square root stuff is well thought

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.

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

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

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

9. Originally Posted by Antigloss
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. Thanks all for your kindly help~Especially to Thantos, thanks a million.

11. /em whisltes
What 9?

12. 9 ?
Originally Posted by Antigloss
Thanks all for your kindly help~Especially to Thantos, thanks a million.

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

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