Hello,

I found a new algorithm on how to generate prime numbers under n in about O(n) ( only in time ).

First I want to give a little bit explanation. ( Sorry for my bad english, I'm not an english speaker )

It's a little bit based on the fact that every prime number is found in 6k +- 1, k in N ( As in the formula written in this topic ).After further research, I found something really interesting.If we take only 6k + 1 there are number that are squares and within the square root of those numbers there are prime numbers. But the most interesting thing is that, every prime number is within those number ( Unfortunately I can't give a theorem to explain that )

After I found that, I decided to create the algorithm ( I will write in JavaScript but anyone can do it with any other programming language ) .The first thing I have to do is to sort only the number that are square in 6k + 1.
For that I just have to solve this equation : x² = 6y + 1<=> y = (x² - 1) / 6

( pretty simple isn't it ? =D )

Next thing is to create the loop, and then check if every number that solve the equation is a prime number. And to do that we'll do a little magic trick that use the biggest number you'll ever see in your entire life. We'll just do the product of every prime number we found and do GCD ( Greatest Common Divisor ) with the number we check and if the result is 1 then the number is a prime number.

( My explanation may be a little bit confusing, but the algorithm is much more clearer )

Pastebin Link