finding prime numbers up to 1000000

[lurtz]

how would i go about doing this?

i would guess that i would put an if statement in a for i : 1..1000000 so that after dividing by all numbers up to itself if it's real it would put something saying that it's a prime.

thanks

[Tony]

wow, your computer will freeze...

on 1,000,000th number you'd have to check if the number is divisible 1,000,000 more times? thats a trillion operations already... thats gonna kill any computer.

I did it using some really cool algorithm before... now if only I could remember it...

Oh ya, now I remember... my teacher taught me this one.

First of all you create an array of 2..1,000,000 as boolean and initialize it all to be 1. Meaning they are all prime untill proven otherwise. Thats a megabite of memory

anyway, then you run a forloop from 2 to square root of your upperlimit... which is 1000 (cutting your loops by 1000times is a VERY good thing).

Now you run a nested loop multiplying that number by everything from 2 to squareroot of max number... this example - 1000. (LOTS AND LOTS of savings).

Now you mutiply your outter counter by inner counter - this number is NOT prime so you change the value in the array to 0. After finishing the loop only the prime numbers in the array will remain as 1 (true).

code:

%declear variable var prime:array 2..1000000 of boolean %initialize all of array for i:2..1000000 prime(i):=true end for %start looping for i:2..1000      for i2:2..1000       prime(i*i2):=false      end for end for

now you just run a loop and print the number if its value is 1(true).

[lurtz]

is that all the code i need?
for some reason i put it in and it says finished executing but nothing happens.

thanks

[Tony]

thats because you just run the code, not read it...

all the code does is it stores the values in the array... you gotta run that array through a loop (2..1000000) and print the number if its set to true.

There seems to be a flaw in the code. Its fine for first few numbers, but I know that its off at higher ranges (I checked...)

also 2nd loop can start from the value of i to make it more efficient. and it should run for longer. such as from i to 1,000,000 / i

I think... also to make it even more efficient you don't have to run the loop if the value is not prime, since all of its multiples were already canceled out. I'll have to get back to this question.

[Tony]

here's the updated version

code:

%declear variable var prime:array 2..1000 of boolean var fstream : int open: fstream, "primes.swat", put %initialize all of array for i:2..1000 prime(i):=true end for %start looping for i:2..10 if prime(i) = true then      for i2:i .. floor(1000/i)       prime(i*i2):=false      end for end if end for for i:2..1000 if prime(i)=true then put : fstream, i end if end for

its in 2-1000 range, but it seems to work fine... largest prime is 997

[Brightguy]

I've written lots of prime number programs, so I just had to reply here. My friend and I even have even had a contest, to see who could come up with the fastest prime number generator... we raced up to 500,000. He originally won with his C++ version, but then I transferred my Turing version to VB and beat him - and I wrote my program in only 15 lines of code!

Here's the Turing version I wrote last summer, this just outputs to the screen whether the number is prime. (I also wrote a version which outputs to a file, but this can be easily modified.)

code:

for n : 2 .. 1000000      var a : real := 1      loop      a += 1           if a > sqrt (n) then                put n, " is a prime number"                exit           end if           exit when n mod a = 0      end loop end for

Amazing that it's only 11 lines! If you wanted, this could list 'em all up to at least 2 billion with lots of time. Cheers!

[Tony]

hey, nice codding, I like how it works, though I don't think its that efficient... I donno... cuz when you get to almost 1,000,000 you still have to run a loop for square root of that number.

But I like the idea behind it

I'll set up a test to race your algorythm against mine and will post results later on.

[Brightguy]

Thanks, that was a fast reply! I just edited the code to use a for statement to cut down the lines to 11, maybe might work a bit faster too.

[Tony]

I run the test... and i won Surprice Surprice, no, I didn't cheat... as a matter of fact, you can run the test yourself and see the results.

both programs run finding all primes from 2 to 100,000 recording the findings in an external file then placing a time stamp of how long it took to execute the program.

My Code and Code of Brighguy are both in files attached, you can download and run the test for yourself.

The only modification to Brightguys program was openning a file and writing to it instead of printing to screen.

In Conclusion - both output files were identical other then the time stamp...

65,726 bytes for mine and 65,727 bytes for Brightguy (time stamp 1 digit longer).

For both final prime was 99991, but it took Brigtguy 25 second to find that out... Tony's code had the answer in 2 second.

Sorry Brightguy, by the time your program will issue the warning, nukes will already hit your bunker

See file attached for both programs.

[Brightguy]

Shoot, it wasn't even close! Nice method - I guess it's faster to calculate all numbers that aren't prime, and then you have a list of all that are.

Congratulations, anyway - I'll look more into your method.

(Oh yeah, one more thing - your method doesn't work in DOS Turing, which was where I wrote my program. Seems to overload the global data size. )

[Tony]

if you didn't already do that, I just posted a tutorial explaining my algorythm under "tutorials" section (as well as basics and yours).

DOS turing has a lot of limitations and is quite bad to use... if anything, it should atleast be winoot. Also I think I can cut the time by more then half if I transfer the program over to C++

And... getting back to original question... the largest prime in the range of up to 1,000,000 is 999,983 603Kb file was generated on Celeron 550 in 19 seconds.

I should come up with some SWAT held competition like this But I'm gonna do that after CCC for sure. Post comments/ideas in general discussion or msg me.