Sieve of Eratosthenes

[MysticVegeta]

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]

[Delos]

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.

[zylum]

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.

[Delos]

Yup. Listen to zylum, he knows what he's talking about....

[codemage]

It's not completely insignificant though.

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

Bubble != selection though.

[zylum]

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.

[MysticVegeta]

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?

[Delos]

It wouldn't . I misread your code.

[Clayton]

dam i remember making that for my compsci class 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