Prime number generator

This is a discussion on Prime number generator within the C Programming forums, part of the General Programming Boards category; Hi all, I'm looking to generate prime numbers. the code starts with p=5, 'p' been a possible prime, then 'd' ...

  1. #1
    Registered User
    Join Date
    Mar 2011
    Posts
    13

    Prime number generator

    Hi all, I'm looking to generate prime numbers. the code starts with p=5, 'p' been a possible prime, then 'd' been the divisor of 'p' to check if it is a prime number or not. where 'x' just increments up changing the value of 'd'. when p/d has no remainders it then checks the value of d to see if it is/isn't equal to 1.

    Code:
    #include <stdio.h>
    main()
    {
    int p,d,x;
    printf("how many primes numbers do you want to find starting from 5?");
    scanf("%d",&y);
    
    p=5;
    x=1;
    start:
    y--;
    if(y>0)
    {d=p-x;
    
    if(p%d!=0)
    {
    x++;
    d=p-x;
    goto start;
    }
    
    else {if(d!=1)
    {p++;
     x=1;
    goto start;}
    
    else{ if(d=1)
    {printf("%d", p);
    p++;
    x++;
    goto start;}
    }}
    
    }
    }
    when i compile and run it. nothing. can't be that hard.

    also if omit the else's, it would still behave the same way right?
    Code:
    #include <stdio.h>
    main()
    {
    int p,d,x,y;
    printf("how many primes numbers do you want to find starting from 5?");
    scanf("%d",&y);
    
    p=5;
    x=1;
    start:
    y--;
    if(y>0)
    {d=p-x;
    
    if(p%d!=0)
    {
    x++;
    d=p-x;
    goto start;
    }
    
    if(d!=1)
    {p++;
     x=1;
    goto start;}
    
    if(d==1)
    {printf("%d", p);
    p++;
    x++;
    goto start;}
    
    }
    
    }

    am i doing something horribly wrong? :O

  2. #2
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,159
    Quote Originally Posted by st00ch View Post
    am i doing something horribly wrong? :O
    1) Your identation
    2) Choice of variable names
    3) goto
    If you understand what you're doing, you're not learning anything.

  3. #3
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    1,602
    Quote Originally Posted by itsme86 View Post
    1) Your identation
    2) Choice of variable names
    3) goto
    Those are horrible for our eyes, minds and sanity, not horribly wrong for the code!
    Devoted my life to programming...

  4. #4
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    1,602
    @st00ch, to find if number is prime you have to do two things. Check if it's divisible by 2 or by any other previous prime number. If any of these are true, that number isn't prime.
    Devoted my life to programming...

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    You'll want some logic like this:

    Code:
    int max, current, i, j, num, root, noprime
    
    get max number from user
    
    current = i = j = noprime = 0 //we have no primes yet
    num = 6    //our first number to test
    while(current < max) {  //loop while we have < max primes
      root = sqrt(num) //test only up to sqrt of num (include math.h)
      for(i = 5; i <= root; i++) {  start test of num
        if(num % i == 0) {    //the actual test with modulo (remainder) arithmetic
          noprime = 1           //it divided into num evenly (no remainder)
          break;                   //so num is not a prime number
        }
      if(noprime == 0)  {    //it's a prime number
        print the number is prime
        ++current              //we have one more prime, currently
      }
      ++num;   //next number to be tested
      noprime = 0  //reset
    }
    This is some of the logic (not runnable code yet), that you can use to help code up your prime number generator program.

    Work with this and if you have questions, post back.

  6. #6
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by Adak View Post
    Code:
    int max, current, i, j, num, root, noprime
    
    get max number from user
    
    current = i = j = noprime = 0 //we have no primes yet
    
    num = 6    //our first number to test
    
    ++num;   //next number to be tested
    Hello Adak...
    A little hint here... An even number cannot be a prime number, we know right away that it can be divided by two... so why bother even testing them?

    Get the max number from the user....
    Start from 3 which is the first odd prime number (1 and 2 are givens).
    Increment your test value by 2 ... num += 2; ... so it stays odd the whole time eliminating the need for a "divide by two" test entirely.

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Howdy Tater, I know the even number trick, not to worry.

    It's not a ready to run program, but a scissor hoist to lift him out of the goto swamp.

  8. #8
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by Adak View Post
    Howdy Tater, I know the even number trick, not to worry.

    It's not a ready to run program, but a scissor hoist to lift him out of the goto swamp.
    Ahhh... yes, C's resident demon... In the 6 or so years I've been using C, I think I've used goto all of once...

  9. #9
    Registered User
    Join Date
    Jun 2005
    Posts
    5,883
    Quote Originally Posted by Sipher View Post
    to find if number is prime you have to do two things. Check if it's divisible by 2 or by any other previous prime number.
    Since 2 is prime, those two things to do can be expressed as one.

    Additionally, to check a value is prime, it is not necessary to check divisibility by all previous primes. To check if a value is prime, it is only necessary to check if it is divisible by any primes not greater than its square root.

    For example, the square root of 7 is approximately 2.64. To check if 7 is prime, it is only necessary to check divisibility by 2. It is not necessary to check divisibility by 3 or 5, since both those values exceed 2.64.
    Right 98% of the time, and don't care about the other 3%.

  10. #10
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    1,602
    Quote Originally Posted by grumpy View Post
    Since 2 is prime, those two things to do can be expressed as one.

    Additionally, to check a value is prime, it is not necessary to check divisibility by all previous primes. To check if a value is prime, it is only necessary to check if it is divisible by any primes not greater than its square root.

    For example, the square root of 7 is approximately 2.64. To check if 7 is prime, it is only necessary to check divisibility by 2. It is not necessary to check divisibility by 3 or 5, since both those values exceed 2.64.
    Well, ok, i didn't know that square root solution. But remember: sqrt is sslllllow!
    2 may be prime but any product 2*n, n ε { 2, 3, 4, ... } isn't. If we have an arbitrary number, checking if it divides perfectly with 2 can save us a lot of CPU cycles.
    Devoted my life to programming...

  11. #11
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by Sipher View Post
    Well, ok, i didn't know that square root solution. But remember: sqrt is sslllllow!
    2 may be prime but any product 2*n, n ε (2, 3, 4, ... ) isn't. If we have an arbitrary number, checking if it divides perfectly with 2 can save us a lot of CPU cycles.
    Combining these two ideas:

    1) only test up to the sqr root of the number, and only find the sqr root ONCE, not every time, through the loop.

    and

    2) test only other prime numbers in the range of 2 through sqr root of the number. Every composite number is the product of a lower prime number.

    Makes for a very quick prime number generator.

    At the lower numbers, #2 doesn't help a lot - but as the primes get further apart, that #2 idea Sipher expressed above, REALLY starts paying HUGE dividends. Without it, the program will start to crawl at numbers greater than about 250,000 or so, depending on your system.

    I don't believe there's a faster way to generate prime numbers, without changing over to an entirely different algorithm (like Rabin-Miller perhaps).

  12. #12
    Registered User
    Join Date
    Jun 2005
    Posts
    5,883
    Quote Originally Posted by Sipher View Post
    Well, ok, i didn't know that square root solution. But remember: sqrt is ssllllow!
    I didn't actually suggest computing the square root.

    For example, consider which circumstances the test x < sqrt(n) and x*x < n give different results.

    Even if one was to compute the square root, it only needs to be computed once, not repeatedly. And there are techniques for, reasonably efficiently, computing an integer square root.
    Quote Originally Posted by Sipher View Post
    2 may be prime but any product 2*n, n ε { 2, 3, 4, ... } isn't. If we have an arbitrary number, checking if it divides perfectly with 2 can save us a lot of CPU cycles.
    We can say the same about any prime number, if you think about it. That is the underlying idea behind the sieve of Eratosphenes.
    Right 98% of the time, and don't care about the other 3%.

  13. #13
    Registered User
    Join Date
    Mar 2011
    Posts
    2
    I am also a newcomer, Just want to know whether the following will be quite faster to find prime numbers.
    Code:
    #include "math.h"
    main()    /* This Generates Prime from 5 to 5000 */
    {
     int i, j, k, s, status;
     for(i=5;i<=5000;i=i+2)             /* i holds value 5 to 5000 */
      {
        s=sqrt(i);   
        status=0;                             /* status changes if found prime */
        for(k=2; k<s; k++)               /* Second Loop checks the possibility of prime */
        {
         if(i%k==0)
          { status++; break;                /* Divisible, hence not prime */
          }
        }
        if(status==0) printf("%d,",i);   /* Prime */
      }
    }

  14. #14
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by chandanpatra View Post
    I am also a newcomer, Just want to know whether the following will be quite faster to find prime numbers.
    In future, please start your own thread for a new question.
    Please don't hijack running threads.

  15. #15
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    @chandanpatra:

    Misses primes 2 and 3, and has limited range since you use just int's. Uses < square root trick and increments number by 2, so it's quick.

    Display of primes needs to be improved much.

    When will k=2, however, in the inner loop? You're only checking odd numbers remember.

    Good algorithm, but not quite accurate yet. Needs a bit more work, imo.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Prime Number Generator
    By abachler in forum Contests Board
    Replies: 76
    Last Post: 12-06-2009, 04:08 PM
  2. xor linked list
    By adramalech in forum C Programming
    Replies: 23
    Last Post: 10-14-2008, 10:13 AM
  3. prime number program with function
    By mackieinva in forum C Programming
    Replies: 17
    Last Post: 09-20-2007, 08:36 AM
  4. Prime Number stops after 29, but why?
    By Daveo in forum C Programming
    Replies: 22
    Last Post: 09-17-2004, 10:55 AM
  5. Random number generator
    By Caze in forum C++ Programming
    Replies: 6
    Last Post: 12-03-2002, 07:10 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21