In pseudo-code: Eratosthenes(n) { a[1] := 0 for i := 2 to n do a[i] := 1 p := 2 while p² < n do { j := p² while (j < n) do { a[j] := 0 j := j+p } repeat p := p+1 until a[p] = 1 } return(a) }
-
-
Show this threadThanks. Twitter will use this to make your timeline better. UndoUndo
-
-
-
There's a lot of fuzz and hype about prime numbers But, what is their utter importance, use, value in the practice? Someone explain me, please
-
I suck at math, but I believe they are used in cryptography. Check this out:https://stackoverflow.com/questions/439870/why-are-primes-important-in-cryptography …
- 4 more replies
New conversation -
-
-
Re the sieve, once accidentally "derived" a differential equation for it. Define Q(x) = ∏(1 - 1/p) taken over all primes p ≤ x, then (using probabilistic smoothing) Q'(x) = - Q(x) Q( √x ) / x => Q(x) = 1 / 2 ln x (in agreement w/ Gauss's estimate)http://babaksjournal.blogspot.com/2008/07/differential-equation-estimating.html …
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
-
-
If anyone wonders why we check till floor(sqrt(n)): If n is composite then we can write n=a·b, where 1 < a ≤ b < n a²≤a·b=n ∴ a ≤ √n
-
Cool. Don’t know much bout composite numbers but will check it out.
- 1 more reply
New conversation -
-
-
Who says you have nothing to do today?
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
-
-
A question to make the interested reader think is: What happens when “n” is very large? How could you sieve segments of 2..n?
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
-
-
sai do site Ana Julia
-
NUNCA
End of conversation
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.