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