algorithm Sieve of Eratosthenes is
    input: an integer n > 1.
    output: all prime numbers from 2 through n.

    let A be an array of Boolean values, indexed by integers 2 to n,
    initially all set to true.

    for i = 2, 3, 4, ..., not exceeding √n do
        if A[i] is true
            for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n do
                set A[j] := false

    return all i such that A[i] is true.

def sieve1(n):
    loops = 0
    numbers = set(range(2, n))
    for i in range(2, int(n ** 0.5) + 1):
        for j in range(i * 2, n, i):
            numbers.discard(j)
            loops += 1
    return sorted(numbers), loops

def primes(upTo):
    isPrime = list(range(upTo))
    for p in range(2,int(upTo**0.5)+1): #p: 2,3,4,...,sqrt(N)
        print(p, isPrime[p])
        if isPrime[p]:
            for multiple in range(p**2,upTo,p): #mult: p^2, p^2+p, p^2+2p, ..., N
                isPrime[multiple] = False
    return [x for x in isPrime[2:] if x]

>>> list(primes(29))
[2, 3, 5, 7, 11, 13, 17, 19, 23]

for x in range(1,999):
 p=n=1
 exec("p*=n*n;n+=1;"*~-x)
 a=b=1
 exec("a*=b*b;b+=1;"*~-int(str(x)[::-1]))
 if p%n and a%b and a!=p:print(x)

def CheckIfProbablyPrime(x):
    return (2 << x - 2) % x == 1

def f(x):return pow(2,x-1,x)==1
for a in range(9,999):
 if f(a)and f(int(str(a)[::-1]))and a!=int(str(a)[::-1]):print(a)

If x is a Carmichael number
    return prime
If x is prime according to Fermat test
    return prime
else
    return composite

f=lambda _:f(print(1))
f()

exec("print(1);open(__file__,'r')"