Re: Prime numberz help!

Discussion in 'C Programming' started by Don, Aug 1, 2007.

  1. Don

    Don Guest

    wrote:
    > Just 4 fun I want to write a program to tell if numberz are prime.
    > I will enter a number, and for all numbers 1 to that number it will say "N is prime" or "N is not prime".
    > And it should be recursuve. What duz that mean?
    > Can u show me how to do it?


    /* Sure! I am always happy to help.
    This program implements a blindingly fast O(n^n) algorithm
    to find prime numbers, using an elegant recursive method. */

    int _(int n, int m, int d, int p)
    {
    int i, r = m != n;
    switch(p)
    {
    case 0:
    for(i=0; d && (i<n); i=_(i,1,d,1))
    r = _(r,_(n,(m<=n)?_(i,m,d,2):0,d-1,0)|!_(i,1,i,0),
    0,2);
    break;
    case 1:
    r = n ? 1 + _(n-1,m,d,1) : m ? 1 + _(n,m-1,d,1) : 0;
    break;
    case 2:
    r = m ? _(n,_(n,m-1,d,2),0,1) : m;
    }
    return r;
    }

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

  2. Don

    santosh Guest

    Don wrote:

    > wrote:
    >> Just 4 fun I want to write a program to tell if numberz are prime.
    >> I will enter a number, and for all numbers 1 to that number it will say
    >> "N is prime" or "N is not prime".
    >> And it should be recursuve. What duz that mean?
    >> Can u show me how to do it?

    >
    > /* Sure! I am always happy to help.
    > This program implements a blindingly fast O(n^n) algorithm
    > to find prime numbers, using an elegant recursive method. */
    >
    > int _(int n, int m, int d, int p)


    Why such an obfuscated name?

    > {
    > int i, r = m != n;
    > switch(p)
    > {
    > case 0:
    > for(i=0; d && (i<n); i=_(i,1,d,1))
    > r = _(r,_(n,(m<=n)?_(i,m,d,2):0,d-1,0)|!_(i,1,i,0),
    > 0,2);
    > break;
    > case 1:
    > r = n ? 1 + _(n-1,m,d,1) : m ? 1 + _(n,m-1,d,1) : 0;
    > break;
    > case 2:
    > r = m ? _(n,_(n,m-1,d,2),0,1) : m;
    > }
    > return r;
    > }
    >
    > /*------------------------------------------
    > Print primes up to the requested value
    > --------------------------------------------*/
    > int main(int argc, char* argv[])
    > {
    > int n, max;
    > scanf("%d",&max);
    > for(n = 2; n <= max; n++)
    > printf("%d is%s prime\n",n, _(n,1,n,0)?"" : " not");
    > return 0;
    > }


    After compiling your program, by fixing missing includes, here's a sample
    session:

    $ ./0014
    78
    2 is prime
    3 is prime
    4 is not prime
    5 is prime

    Infinite loop? Killed after 5 minutes.

    $ ./0014
    10
    2 is prime
    3 is prime
    4 is not prime
    5 is prime

    Maximum CPU usage, no response, killed after 10 minutes.
     
    santosh, Aug 1, 2007
    #2
    1. Advertising

  3. On Aug 1, 1:58 pm, santosh <> wrote:
    > After compiling your program, by fixing missing includes, here's a sample
    > session:
    >
    > $ ./0014
    > 78
    > 2 is prime
    > 3 is prime
    > 4 is not prime
    > 5 is prime
    >
    > Infinite loop? Killed after 5 minutes.
    >
    > $ ./0014
    > 10
    > 2 is prime
    > 3 is prime
    > 4 is not prime
    > 5 is prime
    >
    > Maximum CPU usage, no response, killed after 10 minutes.


    I think his post was meant to be ironic, in response to the original
    request for someone else to do the OP's (on whatever medium it was)
    homework.
     
    Justin Spahr-Summers, Aug 1, 2007
    #3
  4. Don

    santosh Guest

    Justin Spahr-Summers wrote:

    > On Aug 1, 1:58 pm, santosh <> wrote:
    >> After compiling your program, by fixing missing includes, here's a sample
    >> session:
    >>
    >> $ ./0014
    >> 78
    >> 2 is prime
    >> 3 is prime
    >> 4 is not prime
    >> 5 is prime
    >>
    >> Infinite loop? Killed after 5 minutes.
    >>
    >> $ ./0014
    >> 10
    >> 2 is prime
    >> 3 is prime
    >> 4 is not prime
    >> 5 is prime
    >>
    >> Maximum CPU usage, no response, killed after 10 minutes.

    >
    > I think his post was meant to be ironic, in response to the original
    > request for someone else to do the OP's (on whatever medium it was)
    > homework.


    Should've known :)
    Never mind, and, if it *is* meant to be ironic, apologies to Don.
     
    santosh, Aug 1, 2007
    #4
  5. Don

    Don Guest

    On Aug 1, 1:58 pm, santosh <> wrote:
    > Don wrote:
    > > wrote:
    > >> Just 4 fun I want to write a program to tell if numberz are prime.
    > >> I will enter a number, and for all numbers 1 to that number it will say
    > >> "N is prime" or "N is not prime".
    > >> And it should be recursuve. What duz that mean?
    > >> Can u show me how to do it?

    >
    > > /* Sure! I am always happy to help.
    > > This program implements a blindingly fast O(n^n) algorithm
    > > to find prime numbers, using an elegant recursive method. */

    >
    > > int _(int n, int m, int d, int p)

    >
    > Why such an obfuscated name?
    >
    >
    >
    >
    >
    > > {
    > > int i, r = m != n;
    > > switch(p)
    > > {
    > > case 0:
    > > for(i=0; d && (i<n); i=_(i,1,d,1))
    > > r = _(r,_(n,(m<=n)?_(i,m,d,2):0,d-1,0)|!_(i,1,i,0),
    > > 0,2);
    > > break;
    > > case 1:
    > > r = n ? 1 + _(n-1,m,d,1) : m ? 1 + _(n,m-1,d,1) : 0;
    > > break;
    > > case 2:
    > > r = m ? _(n,_(n,m-1,d,2),0,1) : m;
    > > }
    > > return r;
    > > }

    >
    > > /*------------------------------------------
    > > Print primes up to the requested value
    > > --------------------------------------------*/
    > > int main(int argc, char* argv[])
    > > {
    > > int n, max;
    > > scanf("%d",&max);
    > > for(n = 2; n <= max; n++)
    > > printf("%d is%s prime\n",n, _(n,1,n,0)?"" : " not");
    > > return 0;
    > > }

    >
    > After compiling your program, by fixing missing includes, here's a sample
    > session:
    >
    > $ ./0014
    > 78
    > 2 is prime
    > 3 is prime
    > 4 is not prime
    > 5 is prime
    >
    > Infinite loop? Killed after 5 minutes.
    >
    > $ ./0014
    > 10
    > 2 is prime
    > 3 is prime
    > 4 is not prime
    > 5 is prime
    >
    > Maximum CPU usage, no response, killed after 10 minutes.- Hide quoted text -
    >
    > - Show quoted text -


    Not infinite. It takes about an hour to figure out that 6 is not
    prime. But it is recursive, as required!
     
    Don, Aug 1, 2007
    #5
  6. Don

    Guest

    begin quoting santosh <> :
    > Justin Spahr-Summers wrote:

    [snip]
    >> I think his post was meant to be ironic, in response to the original
    >> request for someone else to do the OP's (on whatever medium it was)
    >> homework.


    > Should've known :)
    > Never mind, and, if it *is* meant to be ironic, apologies to Don.


    Whenever I see a function named "_", I conclude that *someone* is
    playing with someone else...

    --
    -----------------------------------------------------------------------------
    "I've got a new entry for our list of words that |
    get a reaction." -Calvin (_Calvin & Hobbes_) | Stewart Stremler
     
    , Aug 1, 2007
    #6
  7. [snips]

    On Wed, 01 Aug 2007 11:27:24 -0700, Don wrote:

    > wrote:
    >> Just 4 fun I want to write a program to tell if numberz are prime.
    >> I will enter a number, and for all numbers 1 to that number it will say "N is prime" or "N is not prime".
    >> And it should be recursuve. What duz that mean?
    >> Can u show me how to do it?

    >
    > /* Sure! I am always happy to help.
    > This program implements a blindingly fast O(n^n) algorithm
    > to find prime numbers, using an elegant recursive method. */



    Blindingly fast O(n^n)? Hmm... think I'll see if I can't try this out
    after I buy another 50 BlueGene systems. :)
     
    Kelsey Bjarnason, Aug 5, 2007
    #7
    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. Replies:
    0
    Views:
    704
  2. CMM

    VS2005 Not ready for prime time

    CMM, Feb 8, 2006, in forum: ASP .Net
    Replies:
    11
    Views:
    710
    Kevin Spencer
    Feb 9, 2006
  3. Peter Luschny

    The tiger sieves prime numbers - fast!

    Peter Luschny, Nov 18, 2004, in forum: Java
    Replies:
    0
    Views:
    381
    Peter Luschny
    Nov 18, 2004
  4. Replies:
    7
    Views:
    841
    John Harrison
    Nov 10, 2005
  5. Jeremy Fischer
    Replies:
    0
    Views:
    222
    Jeremy Fischer
    Jan 16, 2005
Loading...

Share This Page