/me finds an old book containing listings for the BBC microcomputer.

Just incase anyone cares, I thought I''d post the listing of a program to produce a list of primes using the sieve of eratosthenes. Because this program was written to work on a BBC microcomputer (which IIRC had a clock speed of about 2mhz) it should run very fast on a modern 1+ GHz machine.
The code is in BASIC btw - I can''t really be bothered to translate it, it''s not exactly difficult to understand.

10 DIM P(2000)20 REM SET ARRAY ELEMENTS EQUAL TO ONE ( CREATE LIST )30 MAT P = CON40 PRINT "PRIMES FROM 2 - 2000"50 LET F = SQR(2000)60 FOR I = 2 TO 200070 IF P(I) = 0 THEN GOTO 14080 PRINT I;90 IF I > F THEN GOTO 140100 REM REMOVE MULTIPLES FROM LIST ( SET TO ZERO )110 FOR J = I TO 2000 STEP I120 LET P(J) = 0130 NEXT J140 NEXT I150 END 

Also, remember that each line has a line number so that goto''s work etc.

John B

quote:

---

Original post by echeslack
I think LilBudyWizer meant that all primes are 6n+/-1 , not that if you take any positive integer and put it into that formula you will get a prime.

---

That''s more likely I''d say. It was just the wording which put me off...

---

codeka.com - Just click it.

Well, i can show the proof that there is no highest prime but that there are an infinite number of primes. Oh wait, that''s totally irrelevant.

I think that the best way to do this would be to use Sieve of Erasthosthenes with an array populated by numbers of 6n + 1 or 6n - 1. Might take a little algorithm modification to do the job, but should work out to one of the fastest methods possible. Even so, I think you won''t get any higher than a performance of O(n^2).

____________________________________________________________
Direct3D vs. OpenGL

quote:

---

Original post by Anonymous Poster
My gut doesn''t agree with the above post. Mind posting a proof?

---

Well it''s pretty obvious. If it''s 6n, 6n+2, or 6n+4 it''s divisible by 2 and if it''s 6n+3 it''s divisible by 3.

Picking 30 = 2x3x5 you could get something similar - all primes are of the form 30n +/- 1, 30n +/- 7, 30n +/- 11, 30n +/- 13 or something like that.

LilBudyWizer is wrong, not all primes are of the form 6n +/- 1. All twin primes, that is pairs of primes that differ by 2, are of the form 6n +/- 1.

Edit: All except the first pair of twin primes, 3 and 5.

[edited by - Dobbs on April 13, 2002 10:27:36 PM]

The contra-positive is always true if the statement itself is true, but the converse may not be. 6n+/-2 is even and therefore not prime, except of course 2 which is prime. 6n+/-3 is divisible by 3 and therefore is not prime except of course 3 which is prime. 6n is divisible by both 2 and 3 and therefore is not prime. So the only numbers that can be prime are 6n+/-1. Just because every prime can be represented that way though does not mean that every number that can be represented that way is prime. Every apple is a fruit, but that doesn''t make every fruit an apple.

Yes, it can be extended, but becomes certain numbers out of 30, i.e. 2*3*5. The only number you actually drop out is 30n+/-5 over doing 6n+/-1. So you check 8 out of 30 rather than 2 out of 6. You can continue that indefinitely, but the next one is out of 210, so you have to check 48 out of 210. If you notice that is (1*2*4*6)/(2*3*5*7) or 1/2*2/3*4/5*6/7. So if you continue on you reduce it by 1/11, 1/13, 1/17, etc. I think you get it down to checking 8% or so of the numbers using every prime under 100, but your step size by 19 is about 10 million with you having to check about 1.5 million So it can be done, but I don''t know if you would call it either practical nor efficient.

Er my bad. I was confused, what I meant to say was pairs of primes of the form {6n-1,6n+1} (aka {p,p+2}) are known as twin primes. Stupid me.

Pairs of primes of the form {p,p+6} are known as sexy primes.

Those wacky mathematicians.

Mathematix: What about the number 143? Your code would say it is prime, and yet it is 11 * 13.

Firebird Entertainment

quote:

---

Original post by Tron3k
Mathematix: What about the number 143? Your code would say it is prime, and yet it is 11 * 13.

---

You caught me in time! I was just about to delete the post!


Regards,
Mathematix.

For thedo''s for loop... j would only have to go to half the value of i--for instance, in your example of finding primes between 1 and 100, you end up checking 100 with every number between 2 and 99, which is timely, when you really only need to check between 2 and 50. For small ranges this is minor, but for large ranges, like all the primes between 1 and 100000 or something, it gets pretty ridiculous how many calculations you''re doing.
--



WNDCLASSEX Reality;
...
...
Reality.lpfnWndProc=ComputerGames;
...
...
RegisterClassEx(&Reality);


Unable to register Reality...what''s wrong?
---------
Dan Upton
http://0to1.org
http://www20.brinkster.com/draqza

AIM: DigytalSpyder