Prime numbers

Discussion in 'C Programming' started by Don, Aug 31, 2005.

  1. Don

    Don Guest

    > How do you write a program to print the prime numbers
    > up to 1 million?


    #include <stdio.h>

    /* This program implements a blindingly fast O(n^n) algorithm
    to find prime numbers, using an elegant recursive method. */
    int p(int n, int m, int d)
    {
    int i, r = m != n;
    for(i=0; d && (i<n); i++)
    r *= p(n,i*m,d-1)|!p(i,1,i);
    return r;
    }

    /*------------------------------------------
    Print primes up to the requested value
    --------------------------------------------*/
    int main(int argc, char* argv[])
    {
    int n;
    for(n = 2; n<1000000; n++)
    printf("%d is%s prime\n",n, p(n,1,n)?"" : " not");
    return 0;
    }
     
    Don, Aug 31, 2005
    #1
    1. Advertising

  2. Don

    elzacho Guest

    Yeah, that is fast. Any day now I should know if 6 is prime or not...
    :)
     
    elzacho, Aug 31, 2005
    #2
    1. Advertising

  3. #if 0
    Don wrote:
    > > How do you write a program to print the prime numbers
    > > up to 1 million?

    >

    The following program, believe it or not, prints every prime
    (in "Stone-age" or unary code) in order! (subject, like any
    program, to precision and overflow issues on your machine).
    This version is not user-friendly: it may core-dump when
    the primes get too big for it to handle.

    It is based on an invention by John H. Conway, as reported
    in _Ancient Puzzles_ by Dominic Olivastro.

    I''m using this primality program for the Zimmermann Contest.
    #endif

    #include <stdio.h>

    double Prog[] = {
    /* This sequence of 14 fractions *is* the prime
    * generation program !! The function below is just
    * a (very crude) "Minsky-machine" interpreter.
    */
    17/91., 78/85., 19/51., 23/38., 29/33., 77/29., 95/23.,
    77/19., 1/17., 11/13., 13/11., 15/14., 15/ 2., 55/ 1.,
    };

    int ix, oic = 2, nic;
    double f;

    main()
    {
    for (nic = ix = 0; !nic; ix++) {
    f = Prog[ix] * oic + .01;
    nic = (((int)f != (int)(f - .02)) * (int)f);
    }
    oic = nic--;
    if (!(nic + 1 & nic)) {
    do fprintf(stderr, "1");
    while (nic >>= 1);
    fprintf(stderr, "\n");
    }
    main();
    }

    /* Best regards, James */
     
    James Dow Allen, Sep 4, 2005
    #3
  4. Don

    Don Guest

    As I said, it is blindingly fast.

    As in "You'll go blind waiting for it to decide if 8 is prime."
     
    Don, Sep 6, 2005
    #4
  5. James Dow Allen wrote:
    [...]
    > The following program, believe it or not, prints every prime
    > (in "Stone-age" or unary code) in order! (subject, like any
    > program, to precision and overflow issues on your machine).
    > This version is not user-friendly: it may core-dump when
    > the primes get too big for it to handle.

    [...snip...]

    Apparently, only 2, 3, and 5 ("11", "111", and "11111") are prime, as
    the program exits at that point. (Either that, or 7/"1111111" is "too
    big for it to handle".)

    --
    +-------------------------+--------------------+-----------------------------+
    | Kenneth J. Brody | www.hvcomputer.com | |
    | kenbrody/at\spamcop.net | www.fptech.com | #include <std_disclaimer.h> |
    +-------------------------+--------------------+-----------------------------+
    Don't e-mail me at: <mailto:>
     
    Kenneth Brody, Sep 6, 2005
    #5
  6. Don

    Flash Gordon Guest

    Don wrote:
    > As I said, it is blindingly fast.


    What is?

    > As in "You'll go blind waiting for it to decide if 8 is prime."


    Seeing as you provide no context I have no idea what you are talking
    about. Search the group for instructions on how to get context in Google.
    --
    Flash Gordon
    Living in interesting times.
    Although my email address says spam, it is real and I read it.
     
    Flash Gordon, Sep 6, 2005
    #6
  7. On Tue, 06 Sep 2005 19:31:56 +0100, Flash Gordon
    <> wrote:

    >Don wrote:
    >> As I said, it is blindingly fast.

    >
    >What is?
    >
    >> As in "You'll go blind waiting for it to decide if 8 is prime."

    >
    >Seeing as you provide no context I have no idea what you are talking
    >about. Search the group for instructions on how to get context in Google.


    If you don't know what he is talking about then you have nothing to
    contribute to the conversation. Try practicing not contributing.


    Richard Harter,
    http://home.tiac.net/~cri, http://www.varinoma.com
    Save the Earth now!!
    It's the only planet with chocolate.
     
    Richard Harter, Sep 7, 2005
    #7
  8. Don

    Alan Balmer Guest

    On Wed, 07 Sep 2005 15:52:37 GMT, (Richard Harter) wrote:

    >On Tue, 06 Sep 2005 19:31:56 +0100, Flash Gordon
    ><> wrote:
    >
    >>Don wrote:
    >>> As I said, it is blindingly fast.

    >>
    >>What is?
    >>
    >>> As in "You'll go blind waiting for it to decide if 8 is prime."

    >>
    >>Seeing as you provide no context I have no idea what you are talking
    >>about. Search the group for instructions on how to get context in Google.

    >
    >If you don't know what he is talking about then you have nothing to
    >contribute to the conversation. Try practicing not contributing.
    >

    Advising a would-be contributor to provide proper attribution *is* a
    contribution.
    --
    Al Balmer
    Balmer Consulting
     
    Alan Balmer, Sep 7, 2005
    #8
  9. Don

    Randy Howard Guest

    Don wrote
    (in article
    <>):

    > As I said, it is blindingly fast.


    What is?

    Step 1: Learn how to use newsgroups properly.

    Step 2: Learn what newsgroups have the topics you are interested
    in.

    Step 3: Post there, with appropriate context included, so others
    don't have to go searching for the post you are referencing.


    --
    Randy Howard (2reply remove FOOBAR)
     
    Randy Howard, Sep 7, 2005
    #9
  10. Don

    Flash Gordon Guest

    Richard Harter wrote:
    > On Tue, 06 Sep 2005 19:31:56 +0100, Flash Gordon
    > <> wrote:


    <snip a reply with no context>

    >>Seeing as you provide no context I have no idea what you are talking
    >>about. Search the group for instructions on how to get context in Google.

    >
    > If you don't know what he is talking about then you have nothing to
    > contribute to the conversation.


    Incorrect as evidenced by the fact that I *did* contribute. I suspect
    that in this instance most of the regulars here would consider my
    contribution more valuable than yours.

    > Try practicing not contributing.


    I have plenty of practice at that. People who have read this group to
    any real extent will have seen lots of examples of me not contributing.
    However, in this case Don obviously had not yet leant about providing
    context and I decided that I was as good a person as any to point out
    the error of his ways.
    --
    Flash Gordon
    Living in interesting times.
    Although my email address says spam, it is real and I read it.
     
    Flash Gordon, Sep 7, 2005
    #10
  11. Kenneth Brody wrote:
    > James Dow Allen wrote:
    > [...]
    > > The following program, believe it or not, prints every prime
    > > (in "Stone-age" or unary code) in order! (subject, like any
    > > program, to precision and overflow issues on your machine).
    > > This version is not user-friendly: it may core-dump when
    > > the primes get too big for it to handle.

    > [...snip...]
    >
    > Apparently, only 2, 3, and 5 ("11", "111", and "11111") are prime, as
    > the program exits at that point. (Either that, or 7/"1111111" is "too
    > big for it to handle".)


    Well I *did* mention "overflow issues on your machine"!
    (To save bandwidth I tend to be too parsimonious with the
    smiley faces. Note that using gnu's 64-bit arithmetic won't
    be enough to get up to 7.)

    The (amazing) program, due to John Conway, is valid however
    and would print primes with adequate hardware.

    James
     
    James Dow Allen, Sep 9, 2005
    #11
  12. James Dow Allen <> wrote:

    > (To save bandwidth I tend to be too parsimonious with the
    > smiley faces.)


    I really don't believe that the handful (at most) bytes needed for a
    clarifying emoticon are a particular hardship for anyone these days.
    Unless you again neglected to include one...

    --
    Christopher Benson-Manica | I *should* know what I'm talking about - if I
    ataru(at)cyberspace.org | don't, I need to know. Flames welcome.
     
    Christopher Benson-Manica, Sep 9, 2005
    #12
  13. Oh, very good. A C code (translated of ForTran). Ok, very good. I'am
    really like.
    But...
    Sometimes, we want to build ours own tools (poor e simply tools, is
    true) and if that is her case... I advise you that begin like this:
    * The only prime number that is "no-odd" is 2.
    * Then you don't want verify if 4, 6, 8, 10, 12 is prime.
    * A good algorhitm , in this case, probally is recursive.

    Nice!
     
    Leonardo Andrade, Sep 9, 2005
    #13
  14. "Leonardo Andrade" <> writes:
    > Oh, very good. A C code (translated of ForTran). Ok, very good. I'am
    > really like.
    > But...
    > Sometimes, we want to build ours own tools (poor e simply tools, is
    > true) and if that is her case... I advise you that begin like this:
    > * The only prime number that is "no-odd" is 2.
    > * Then you don't want verify if 4, 6, 8, 10, 12 is prime.
    > * A good algorhitm , in this case, probally is recursive.


    Look up "Sieve of Eratosthenes". It's about 2200 years old.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    We must do something. This is something. Therefore, we must do this.
     
    Keith Thompson, Sep 9, 2005
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Peter Luschny

    The tiger sieves prime numbers - fast!

    Peter Luschny, Nov 18, 2004, in forum: Java
    Replies:
    0
    Views:
    361
    Peter Luschny
    Nov 18, 2004
  2. Chris

    Prime Numbers

    Chris, Oct 31, 2003, in forum: C++
    Replies:
    4
    Views:
    583
    Josephine Schafer
    Oct 31, 2003
  3. AshifToday

    Composite and Prime Numbers

    AshifToday, May 22, 2005, in forum: C++
    Replies:
    0
    Views:
    2,763
    AshifToday
    May 22, 2005
  4. Tim Churches

    Safe prime numbers in Python

    Tim Churches, Jan 14, 2004, in forum: Python
    Replies:
    1
    Views:
    540
    Paul Rubin
    Jan 14, 2004
  5. Jeremy Fischer
    Replies:
    0
    Views:
    188
    Jeremy Fischer
    Jan 16, 2005
Loading...

Share This Page