sieve of eratosthenes implementation

[perfringo]

"The beginning of wisdom is the definition of terms." --Socrates

I feel that we argue about different subjects. My point is that these codes are implementation of algorithm (as it not uses trial division).

No argument about whether your code is much simpler and easier to understand. Yes, it is better suited for explanation. I can only plea that OP did not posted it under 'Homework' but in 'General coding help'.

For mimicking paper-and-pencil sieve following approach can be used (uses numpy so not for total beginners, but code itself is very simple):

import numpy as np

def primes(max_value):
    sieve = np.ones(max_value + 1, dtype=np.bool)    # create array of ones/True-s for all values in range, starting from 0
    sieve[:2] = False                                # mark 0 and 1 as False
    for i in range(2, int(max_value**0.5)+1):        # for range 2 to square root of max_value + 1 
        if sieve[i]:                                 # if value on index is True
            sieve[i*i::i] = False                    # mark values False starting from square of value with step of value

    primes = np.nonzero(sieve)[0]                    # primes are all non-zero/non-False (True) values; get True indices
    return primes

Some explanations:

- 'sieve' is representing sieve where initially all 'numbers' are 'True' (primes). 'Numbers' here are actually their indices; True and False representing whether they are marked as primes or non-primes.
- Python uses zero-based indices so we set two first values at indices 0 and 1 to False (non-prime)
- we loop in range of 2 to max value of possible divisor (square root of max_value + 1)
- first iteration with value 2 marks all even values False (non-prime)
- all numbers marked as non-primes starting from square of the number with the step of the number (evens were marked as non-primes in first iteration, so no need to start from multiple of two)
- we get 'sieve' where primes are True and non-primes are 'False'
- we take indices of primes/True values and return them

There is sieve on numbers, non-primes are marked but kept. Only non-marked i.e primes are taken 'out'.

This is pretty fast compared to standard Python loops. Finding primes with max_value of 1_000_000 is practically instant (78_498 primes) with max_value 1_000_000_000 on my machine it took around 10 seconds (50_847_534 primes).