3h
comment Sieve of Eratosthenes without arrays?
as long as you give proper attribution, as per SO's license. So, instead of copying, just write it anew yourself. Without looking. :) Change something in it, like count by 1 instead of by 2; or count by 6.
14h
comment Sieve of Eratosthenes without arrays?
@imRentable did you miss my comments? I show how it can be done, although for a relatively low top value limit. Up to a 100 it is very easily done. See the answer I linked to.
1d
comment Sieve of Eratosthenes without arrays?
actually, to get to 10,000 we only need to keep track of multiples of 25 primes (the ones below 100). But that's pushing it, with 25 explicit variables. And the top limit can't be increased.
1d
comment Sieve of Eratosthenes without arrays?
@tobias_k incremental sieve replaces the contiguous array with a priority queue of primes' multiples, creating a "sliding" sieve (see it simulated here). But priority queue is a collection too.
1d
comment Sieve of Eratosthenes without arrays?
The sieve (of E.) is about remembering the composites, but that doesn't change the conclusion. Without any collections we're reduced to trial division or some other kind of primality testing -- which is not sieving. With the top limit sufficiently low we can do it without arrays by simulating a priority queue of multiples with just naked variables. But that's impractical for much above 100.
2d
comment Find the nth prime between 1 and 1,000,000 in under 3 minutes - follow-up
trial division is not analogous to the sieve of Eratosthenes. trial division is filtering the numbers one-by-one by a predicate, the sieve is constructing whole lists of numbers that would be eliminated by this filtering (for each prime it enumerates its multiples).
2d
comment Find the nth prime between 1 and 1,000,000 in under 3 minutes - follow-up
"(like Eratosthenes did)"? we don't even know whether he incremented at all. For all we know he just counted (incrementing by 1) - e.g. "mark every 5th number" while counting 1,2,3,4,5,1,2,3,...
Oct
22
comment Java Prime calculator according to Sieve of Eratosthenes
replace j * i <= n; loop condition with j <= n/i.
Oct
21
comment How to implement an efficient infinite generator of prime numbers in Python?
yeah, it was pretty exciting to realize (in 2004 :) ) the need to synchronize the sieve on the squares of primes themselves. Learning Haskell, I made an error when re-writing a "demo" definition primes = map head (iterate sieve [2..]) where sieve (p:xs) = [x | x<-xs, x `rem` p /= 0] as a recursive function, and it was very slow. When I corrected the error it was still very slow, so I tried to understand why...
Oct
20
revised What is the space complexity of a prime sieve with data in proportion to number of primes?
added 133 characters in body
Oct
20
answered What is the space complexity of a prime sieve with data in proportion to number of primes?
Oct
20
comment What is the space complexity of a prime sieve with data in proportion to number of primes?
N above is the upper limit, so N ~= n log(n) and the complexity in that answer is O( sqrt(n log(n))/log(n)) = O( sqrt( n/log(n) )) for n primes.
Oct
20
comment What is the space complexity of a prime sieve with data in proportion to number of primes?
this answer demonstrates a sieve of Eratosthenes with space complexity of O( sqrt(N)/log(N) ) - not counting the produced primes of course.
Oct
20
comment Find primes using "naive" algorithm
@sanchises 6 = 2*3. and next comes 30=2*3*5.
Oct
20
comment How to implement an efficient infinite generator of prime numbers in Python?
did I say thank you? I should've, when I upvoted (back in April, as SO says to me). :) This is very nice, esp. the asserts. Of course the core beauty is by the initial author(s).
Oct
20
comment Checking for the nth prime number between 1 and 1,000,000, must compute 1,000,000th in under 3 minutes
the code in an answer of mine on SO finds the 1,000,000th prime in 8 seconds on ideone (which is about 3x slower than any common box). It implements an incremental sieve of Eratosthenes. Check it out, :) or Tim Peters's Python 3 re-write of it which is "significantly faster" yet.
Oct
20
comment Checking for the nth prime number between 1 and 1,000,000, must compute 1,000,000th in under 3 minutes
@PieterB that means primes under 1,000,000 in magnitude; but the 1mlnth prime is ~ 15.5 million. But that just means 1001 should be replaced with 3940. no biggie.
Oct
20
comment Given a range of values 1 though n, what is the most efficent way to split that list into m "nearly equal" sub-ranges?
@augustss by your algorithm, splitting 27 in 7 gives 27/7=3, 27%7=6 => 6*4+(7-6)*3, so splitting 25 into 6 nearly-equal ranges gives 25/6=4, 25%6=1 => 1*5+(6-1)*4, which is just as good. I was a bit confused there, thought about a different problem (splitting into nearly-equaled portions, given a maximal size).
Oct
19
revised Haskell - span elem: evaluation
typo
Oct
19
revised Translate Haskell code into Standard ML (combinations with repetition)
added 113 characters in body
1 2 3 4 5