Easiest way: make an array in which you store the primes found. Check if the current number is divisable by any of them, if not it's another prime. See Eratosthenes' sieve (Zeef van Eratosthenes).

0

kimos123Author Commented:

i want to make it without area's it should be very easy if we have 2 loops
one to loop the numbers and one to loop the % number from 1 to the primenumber or from the primenumber to 1

but im stuck with the loops im not so good in loops

good illustration of the sieve is here: http://www.faust.fr.bw.schule.de/mhb/eratosiv.htm
The array only contains true/false flags, the indexes into the array are the numbers that are prime or not...

other than that, simple way is to test against every odd number between 2 and sqrt( number ), or even better (well... arguable) against all primes between 2 and sqrt( number )...

// dodgy recursive function....
function int isprime( int number ) {
int i;
// Special cases...
if( number <= 2 ) {
return 0;
}

for( i = 3; i <= sqrt( number ); i+=2 ) {
if( isprime( i ) ) {
if( number % i == 0 ) {
return 0;
}
}
}
return 1;
}

0

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

starting with p == 1 is incorrect as sjef_bosman points out... definition of prime is an integer not devisible by any integer between 2 and itself (inclusive). Testing 2, and then every prime upto sqrt(number) is sufficient, although, this is obviously recursive (unless using a sieve as described above). For small numeric sets, simply testing 2 and all odd numbers upto sqrt(number) is sufficient, but how useful are small prime numbers?
The sieve mechanism is simple to implement, even for ranges in the 1000s...

unsigned char a[SIEVE_SIZE];
int i,j;
memset( a, 1, SIEVE_SIZE );

a[0] = a[1] = 0;

for( i = 2; i < SIEVE_SIZE; ) {
for( j = 2*i; j < SIEVE_SIZE; j+= i ) {
a[j] = 0;
}
do {
i++;
} while( !a[i] );
}
for( i = 0; i != SIEVE_SIZE; i++ ) {
if( a[i] ) {
printf( "Prime: %d\n", i );
}
}

Of course the idea is not wrong, it's just very time-consuming: if the value to be tested is 10000, you have to divide 999 times whereas witha sieve you divide max 100 time (i.e. sqrt(10000)), and in practice only some 20 times. So you solved the problem in an O(n*n) algorithm, but it can be done in O(n).

0

kimos123Author Commented:

nevermind about the loop i made it
i just want an explanation for

unsigned char a[SIEVE_SIZE];
int i,j;
memset( a, 1, SIEVE_SIZE );

a[0] = a[1] = 0;

for( i = 2; i < SIEVE_SIZE; ) {
for( j = 2*i; j < SIEVE_SIZE; j+= i ) {
a[j] = 0;
}

thanks
do {
i++;
} while( !a[i] );
}
for( i = 0; i != SIEVE_SIZE; i++ ) {
if( a[i] ) {
printf( "Prime: %d\n", i );
}
}

an real interesting exercise to write the function with zero variable "area" at all... i.e. without any variables, just the argument to play with... reminds me of my college days, getting LISP practicals to generate poetry without using any variables at all...