Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
finding prime numbers up to 1000000
Author Message
lurtz

Posted: 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

Tony

Posted: Thu Feb 13, 2003 4:44 pm   Post subject: (No subject)

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).
Tony's programming blog. DWITE - a programming contest.
lurtz

Posted: Thu Feb 13, 2003 4:54 pm   Post subject: (No subject)

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

thanks
Tony

Posted: Thu Feb 13, 2003 5:15 pm   Post subject: (No 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... 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's programming blog. DWITE - a programming contest.
Tony

Posted: Thu Feb 13, 2003 5:27 pm   Post subject: (No 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
Tony's programming blog. DWITE - a programming contest.
Brightguy

Posted: 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!

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

Posted: Fri Feb 14, 2003 2:40 pm   Post subject: (No 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

I'll set up a test to race your algorythm against mine and will post results later on.
Tony's programming blog. DWITE - a programming contest.
Brightguy

Posted: 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.

Tony

Posted: Fri Feb 14, 2003 3:06 pm   Post subject: prime run

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.

tony.t
Description:
 Prime finder by Tony

Filename:  tony.t
Filesize:  516 Bytes

brightguy.t
Description:
 Prime Finder by BrighGuy

Filename:  brightguy.t
Filesize:  431 Bytes

Tony's programming blog. DWITE - a programming contest.
Brightguy

Posted: Fri Feb 14, 2003 3:35 pm   Post subject: Re: Primes

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

Posted: Fri Feb 14, 2003 5:22 pm   Post subject: (No 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++

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.
Tony's programming blog. DWITE - a programming contest.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 11 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: