"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):
- '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).
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 primesSome 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).
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.