Computer Science Canada

Sieve of Eratosthenes
Author:  MysticVegeta [ Tue Apr 25, 2006 6:10 pm ]
Post subject:  Sieve of Eratosthenes
Remember in middle school when we had to calculate methods by writing all the numbers down and incrementing the divisor and crossing out all of its multiples until we reach the number? Well a same concept has been implemented into this algorithm to calculates primes really fast! so now there is no way your program can timeout in contests even with Turing!!!! Pretty self explanatory code:

code:
var n := 100000
var timeTaken : int
var primes : array 1 .. n of boolean

primes (1) := false

for i : 1 .. n
    primes (i) := true
end for

for i : 2 .. ceil (sqrt (n))
    for j : i * 2 .. n by i
        primes (j) := false
    end for
end for

clock (timeTaken)
put "It took ", (timeTaken / 1000) : 0 : 2, " seconds to calculate primes from 1 to ", n, "."
[/code]
Author:  Delos [ Tue Apr 25, 2006 7:22 pm ]
Post subject: 
Mystic, you've been around here long enough to know that we've seen this posted at least eleventy billion times [/SNL reference].
I would like to point out that you should optimize your code just a little. That first for loop (initializing all to true) is unnecassary. Incorporate that into an if statement in your actual check - will cut down your number of computations by n - which can be a lot at lower values.
Author:  zylum [ Tue Apr 25, 2006 8:53 pm ]
Post subject: 
cutting the algorithm by N is insignificant since the entire algo is O(N^2). If you've ever done algorithm complexity youd learn that you only keep the term with highest degree. besides, i dont see how it will work without initializing the array.
Author:  Delos [ Tue Apr 25, 2006 10:22 pm ]
Post subject: 
Yup. Listen to zylum, he knows what he's talking about...Laughing.
Author:  codemage [ Wed Apr 26, 2006 8:16 am ]
Post subject: 
It's not completely insignificant though.

Bubble and selection sort are both N^2 becuase we drop the lower terms.

Bubble != selection though.
Author:  zylum [ Wed Apr 26, 2006 1:00 pm ]
Post subject: 
it is almost completely insignificant, especially for larger values of N. btw, time complexity isnt necessarily to see how fast your algo is, it is more to determine how much slower it will be for an increase of input. so you know an N^2 algo will be about 4 times slower for twice as much input. even if you have that extra loop that adds N to the time, over all, again especially with larger Ns, that extra N will be almost insignificant.
Author:  MysticVegeta [ Wed Apr 26, 2006 1:35 pm ]
Post subject: 
It has been posted before? damn I must have missed it, I just thought it was cool and better than creating a function and running a loop from 2 to sqrt(N) everytime.. Anyways, how would it work without intializing the array?
Author:  Delos [ Wed Apr 26, 2006 4:33 pm ]
Post subject: 
It wouldn't Laughing. I misread your code.
Author:  Clayton [ Wed Apr 26, 2006 4:46 pm ]
Post subject: 
dam i remember making that for my compsci class Crying or Very sad Crying or Very sad i like the way you did it, except i made mine so the user could input the highest number to search to and i kept a counter instead of an array (so i didnt have to initialize it) it worked pretty good, although i wish i had the algorithim you had, mine just checked for all of the factors for it, and if it only had 2 (1 and itself) then it was a prime number and outputted it to the screen

:


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

Terms of Use | Privacy Policy