Computer Science Canada

finding prime numbers up to 1000000
Author:  lurtz [ Thu Feb 13, 2003 4:21 pm ]
Post subject:  finding prime numbers up to 1000000
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
Author:  Tony [ Thu Feb 13, 2003 4:44 pm ]
Post subject: 
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... Confused

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 Wink

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).
Author:  lurtz [ Thu Feb 13, 2003 4:54 pm ]
Post subject: 
is that all the code i need?
for some reason i put it in and it says finished executing but nothing happens.

thanks
Author:  Tony [ Thu Feb 13, 2003 5:15 pm ]
Post subject: 
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... Confused 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.
Author:  Tony [ Thu Feb 13, 2003 5:27 pm ]
Post subject: 
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 Very Happy
Author:  Brightguy [ Fri Feb 14, 2003 2:32 pm ]
Post subject:  Re: Primes
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! Very Happy

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! Very Happy
Author:  Tony [ Fri Feb 14, 2003 2:40 pm ]
Post subject: 
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 Wink

I'll set up a test to race your algorythm against mine and will post results later on.
Author:  Brightguy [ Fri Feb 14, 2003 2:49 pm ]
Post subject:  Re: Primes
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.
Author:  Tony [ Fri Feb 14, 2003 3:06 pm ]
Post subject:  prime run
I run the test... and i won Very Happy 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 Wink

See file attached for both programs.
Author:  Brightguy [ Fri Feb 14, 2003 3:35 pm ]
Post subject:  Re: Primes
Shoot, it wasn't even close! Rolling Eyes 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. Smile

(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. Wink)
Author:  Tony [ Fri Feb 14, 2003 5:22 pm ]
Post subject: 
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++ Wink

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

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

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy