Improve company productivity with a Business Account.Sign Up

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 875
  • Last Modified:

Prime Numbers

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      
primenumber % (1 to  primenumber -1 )  

plz help me im stuck
thanks in advance
0
kimos123
Asked:
kimos123
  • 10
  • 8
  • 6
1 Solution
 
Sjef BosmanGroupware ConsultantCommented:
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
0
 
cjjcliffordCommented:
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
Worried about phishing attacks?

90% of attacks start with a phish. It’s critical that IT admins and MSSPs have the right security in place to protect their end users from these phishing attacks. Check out our latest feature brief for tips and tricks to keep your employees off a hackers line!

 
cjjcliffordCommented:
sorry... special cases above are wrong...

code snippet should be:

// Special cases
if( number < 2 )  { return 0; }
if( number == 2 )  { return 1; }
0
 
Sjef BosmanGroupware ConsultantCommented:
If you start with p==1, a%p will always be zero.
0
 
kimos123Author Commented:
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++;

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

}    

 a++;

}

}
------------------------
0
 
Sjef BosmanGroupware ConsultantCommented:
Interesting filename... ;)

Remove the word "function".
0
 
kimos123Author Commented:
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
 
cjjcliffordCommented:
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
 
cjjcliffordCommented:
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
 
cjjcliffordCommented:
obvious possible overflow bug with my sieve impl. but that can be an exercise (the do { } while() loop...)
0
 
kimos123Author Commented:
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 1: firstprimenumber
prime 2: secondprimenumber
prime 3: etc...

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

thanks in advance
0
 
Sjef BosmanGroupware ConsultantCommented:
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 );
        }
    }
0
 
cjjcliffordCommented:
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
 
kimos123Author Commented:
thanks  cjjclifford  & sjef_bosman for the help.  
im glade experts like you guys are in this forum :)
0
 
Sjef BosmanGroupware ConsultantCommented:
Next time, try a question with 500 points: they'll be all over you!
0
 
cjjcliffordCommented:
you mean it wasn't! oh, darn :-)
0
 
Sjef BosmanGroupware ConsultantCommented:
That'll teach you to supply the whole solution!

Sjef (LOL)
0
 
cjjcliffordCommented:
ironically, the slow, inefficient solution was accepted, rather than the sieve impl....
0
 
Sjef BosmanGroupware ConsultantCommented:
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
 
cjjcliffordCommented:
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
 
Sjef BosmanGroupware ConsultantCommented:
I somehow managed to slip through LISP... I'll think about this one, tomorrow. Maybe something for the riddles TA?
0
 
cjjcliffordCommented:
indeed maybe... its an interesting idea though, pure functional programming using C, which is traditionally not used for that...
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Improve Your Query Performance Tuning

In this FREE six-day email course, you'll learn from Janis Griffin, Database Performance Evangelist. She'll teach 12 steps that you can use to optimize your queries as much as possible and see measurable results in your work. Get started today!

  • 10
  • 8
  • 6
Tackle projects and never again get stuck behind a technical roadblock.
Join Now