Prime numbers

[Don]

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;
}

 

[elzacho]

Yeah, that is fast. Any day now I should know if 6 is prime or not...

 

[James Dow Allen]

#if 0
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 */

 

[Don]

As I said, it is blindingly fast.

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

 

[Kenneth Brody]

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:[email protected]>

 

[Flash Gordon]

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.

 

[Richard Harter]

What is?


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, (e-mail address removed)
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

 

[Alan Balmer]

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.

 

[Randy Howard]

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.

 

[Flash Gordon]

On Tue, 06 Sep 2005 19:31:56 +0100, Flash Gordon


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.

 

[James Dow Allen]

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

 

[Christopher Benson-Manica]

(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...

 

[Leonardo Andrade]

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!

 

[Keith Thompson]

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.