# Re: Prime numberz help!

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

1. ### DonGuest

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

2. ### santoshGuest

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

3. ### Justin Spahr-SummersGuest

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
4. ### santoshGuest

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
5. ### DonGuest

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
6. ### 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
7. ### Kelsey BjarnasonGuest

[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