Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
Solved

# Prime Numbers

Posted on 2004-09-28
Medium Priority
866 Views
hi there,
im trying to make a prog  that generate the first  100 prime numbers
here is my code:

#include <stdio.h>
int main(void)
{
int x,a,f,p,teller;
a=2;
f=0;
//p=a-1;
for(x=1 ; x<1000;x++){

//for(p=1; p<a; p++){

if ((a%p !=0) &&  f<100){

for(p=1; p<a; p++){

//    for(p=a; p>0; p--) {

// print("Priem
f++;

printf("Priemgetal %i: %i \n",f,a );

}
// p++;
a++;

}
//p++;
}

}
----------------------

and its not working   here is how i want to make it i dont know if its good
prime number is
primenumber % primenumber -1   << and it have to loop intil 1

anyone can help me with it ?

other possible way is

plz help me im stuck
0
Question by:kimos123
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 10
• 8
• 6

LVL 46

Expert Comment

ID: 12169163
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

Author Comment

ID: 12169237
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
0

LVL 11

Expert Comment

ID: 12169346
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

LVL 11

Expert Comment

ID: 12169361
sorry... special cases above are wrong...

code snippet should be:

// Special cases
if( number < 2 )  { return 0; }
if( number == 2 )  { return 1; }
0

LVL 46

Expert Comment

ID: 12169463
0

Author Comment

ID: 12169482
kut.c:3: syntax error before `int'
kut.c: In function `isprime':
kut.c:11: warning: type mismatch in implicit declaration for built-in function `sqrt'

i have this until now and i get error compiling

------------------------------------
#include <stdio.h>

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

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

int main(void)
{
int x,a,f,p,teller;
a=2;
f=0;

for(x=1 ; x<1000;x++){

if (isprime(a) &&  f<100){
f++;

}

a++;

}

}
------------------------
0

LVL 46

Expert Comment

ID: 12169506
Interesting filename... ;)

Remove the word "function".
0

Author Comment

ID: 12169534
lol sjef   yea i been trying it for 2 days now...  i coudnt hold it so i used this name :)

i still got the error    i removed the function  word  and i dont have the first syntax error but i still got:

kut.c: In function `isprime':
kut.c:11: warning: type mismatch in implicit declaration for built-in function `sqrt'
0

LVL 11

Expert Comment

ID: 12169579
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 );
}
}
0

LVL 11

Expert Comment

ID: 12169596
yup, not sure why I put "function" in there...

also, #include <math.h> to get sqrt().

Also, sqrt() expects double, not int, but the implicit cast should be ok, once the #include is there...
0

LVL 11

Expert Comment

ID: 12169618
obvious possible overflow bug with my sieve impl. but that can be an exercise (the do { } while() loop...)
0

Author Comment

ID: 12169660
cjjclifford thanks alot  it worked
but is my idea wronge?  about looping and testing the mod (%) ?

and how can i put a loop in it so it display
prime 3: etc...

and could you please explane what you did exactly becouse i dont understand it.

0

LVL 46

Expert Comment

ID: 12169895
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

Author Comment

ID: 12169898
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 );
}
}
0

LVL 11

Accepted Solution

cjjclifford earned 80 total points
ID: 12169899
Looping and testing mod will work, but is not as efficient as possible.

int i,j,prime;
for( i = 2; i != 100; i++ ) {
prime = 1;
for( j = 2; j != i; j++ ) {
if( i % j == 0  ) {
prime = 0;
break;
}
}
if( prime ) {
printf( "%d is prime\n", i );
}
}

0

Author Comment

ID: 12170043
thanks  cjjclifford  & sjef_bosman for the help.
im glade experts like you guys are in this forum :)
0

LVL 46

Expert Comment

ID: 12170166
Next time, try a question with 500 points: they'll be all over you!
0

LVL 11

Expert Comment

ID: 12170196
you mean it wasn't! oh, darn :-)
0

LVL 46

Expert Comment

ID: 12170688
That'll teach you to supply the whole solution!

Sjef (LOL)
0

LVL 11

Expert Comment

ID: 12170822
ironically, the slow, inefficient solution was accepted, rather than the sieve impl....
0

LVL 46

Expert Comment

ID: 12170935
But that's what he asked for (without "area") :(
Ah say, you were so well on your way, now how could I barge in?

Sjef ;)
0

LVL 11

Expert Comment

ID: 12171075
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...
0

LVL 46

Expert Comment

ID: 12171193
I somehow managed to slip through LISP... I'll think about this one, tomorrow. Maybe something for the riddles TA?
0

LVL 11

Expert Comment

ID: 12171363
indeed maybe... its an interesting idea though, pure functional programming using C, which is traditionally not used for that...
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were smallâ€¦
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see soâ€¦
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.
###### Suggested Courses
Course of the Month9 days, 4 hours left to enroll