Dec-21-2019, 11:35 AM
(Dec-20-2019, 08:29 PM)Clunk_Head Wrote: Neither of those is the sieve of eratosthenes. While they both find prime numbers, this post asked a about a very specific method.
I disagree with this assessment. OP asked: "Can anyone provide me a simple implementation of sieve of eratosthenes algorithm"
One should clarify what is algorithm and what is implementation.
Quote:Sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2. The multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them that is equal to that prime.[1] This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.
This algorithm is about eliminating multiples of each prime (non-prime) and from that follows that remaining numbers are primes.
How its done is 'implementation detail'. It doesn't matter if 'marking' is done by creating full list in advance or filtered out on the go. As long it's uses multiples of primes it's implementation of Sieve of Eratostehenes algorithm.
I'm not 'in'-sane. Indeed, I am so far 'out' of sane that you appear a tiny blip on the distant coast of sanity. Bucky Katt, Get Fuzzy
Da Bishop: There's a dead bishop on the landing. I don't know who keeps bringing them in here. ....but society is to blame.
Da Bishop: There's a dead bishop on the landing. I don't know who keeps bringing them in here. ....but society is to blame.