*Sieve of Eratosthenes* is an algorithm for finding every [[Prime numbers|prime]] up to any given limit.
# Python Implementation
```run-python
def sieve(n):
prime = [0,0]+ [1]*(n-1) #assume all vals prime apart from 0 and 1
#sieve process below, so prime[i] becomes 0 if i is not prime
p = 2
while 2*p <= n:
for i in range(2*p,n+1,p):
prime[i] = 0
p += 1
while prime[p] == 0:
p = p + 1
#create list to return
ls = []
for i in range(2,n+1):
if prime[i]:
ls = ls+[i]
return ls
# test
print(sieve(100000))
```
# Application
See **application** [[Prime Factorisation]].