from math import sqrt
from time import process_time
import sys

''' Définitions de fonctions '''

# Exercice 1

def Eratosthene(n):
    if n<2:
        return []
    isprime = (n+1)*[True]
    isprime[0]=False
    isprime[1]=False
    imax = int(sqrt(n))
    for i in range(2,imax+1):
        if isprime[i]:
            j0=2*i
            for j in range(j0,n+1,i):
                isprime[j]=False
    res=[]
    for i in range(n+1):
        if isprime[i]:
            res.append(i)
    return res

def Eratosthene2(n):
    if n<2:
        return []
    isprime = (n+1)*[True]
    isprime[0]=False
    isprime[1]=False
    imax = int(sqrt(n))
    for i in range(2,imax+1):
        if isprime[i]:
            j0=i*i
            for j in range(j0,n+1,i):
                isprime[j]=False
    res=[]
    for i in range(n+1):
        if isprime[i]:
            res.append(i)
    return res


def Eratosthene3(n):
    if n<2:
        return []
    isprime = (n+1)*[True]
    isprime[0]=False
    isprime[1]=False
    for j in range(4,n,2):
        isprime[j]=False
    #res=[2]
    imax = int(sqrt(n))
    for i in range(3,imax+1,2):
        if isprime[i]:
            #res.append(i)
            j0=i*i
            for j in range(j0,n+1,i):
                isprime[j]=False
    res=[2]
    for i in range(3,n+1,2):
        if isprime[i]:
            res.append(i)
    return res


# Exercice 2

class Case:
    pred=None
    succ=None
    
'''def init(i):
    res = Case()
    res.succ=i+2
    res.pred=i-2
    return res'''
    
def deletecase(i,tab):
    p=tab[i].pred
    s=tab[i].succ
    if p:
        tab[p].succ = s
    if s:
        tab[s].pred = p

def Eratosthenelinear(n):
    if n<2:
        return []
    if n == 2:
        return [2]
    if n <= 4:
        return [2,3]
    n -=  1-n%2 #inutile de considérer une dernière case paire, qui ne sera pas un nombre premier
    primes = [Case() for i in range(n+1)]
    primes[2].succ=3
    for i in range(5,n,2):
        primes[i].succ=i+2
        primes[i].pred=i-2
    primes[3].succ=5
    primes[n].pred=n-2
    imax = int(sqrt(n))
    res=[2]
    i = 3
    while(i<=imax):
        res.append(i)
        j=i
        x=i*j
        multiples=[]
        while x<=n:
            multiples.append(x)
            j=primes[j].succ
            x=i*j
        #print("Multiples de",i,":",multiples)
        for x in multiples:
            deletecase(x,primes)
        i = primes[i].succ
    while i:
        res.append(i)
        i = primes[i].succ
    return res


def Eratosthene4(n):
    if n<2:
        return []
    if n == 2:
        return [2]
    if n <= 4:
        return [2,3]
    n -=  1-n%2 #inutile de considérer une dernière case paire, qui ne sera pas un nombre premier
    succ = (n+1)*[None]
    pred = (n+1)*[None]
    succ[2]=3
    pred[3]=2
    succ[3]=5
    pred[n]=n-2
    for i in range(5,n,2):
        succ[i]=i+2
        pred[i]=i-2
    imax = int(sqrt(n))
    res=[2]
    i = 3
    while(i<=imax):
        res.append(i)
        j=i
        x=i*j
        multiples=[]
        while x<=n:
            multiples.append(x)
            j=succ[j]
            x=i*j
        for x in multiples:
            p = pred[x]
            s = succ[x]
            if p:
                succ[p]=s
            if s:
                pred[s]=p
        i = succ[i]
    while i:
        res.append(i)
        i = succ[i]
    return res


''' Tests '''

if __name__=='__main__':
    
    def test(f,x):
        start=process_time()
        res=f(x)
        print("Le résultat est",res,"et a été calculé en",process_time()-start,"secondes.")
    
    
    n=10000000
    test(Eratosthene,n)
    test(Eratosthene2,n)
    test(Eratosthene3,n)
    #test(Eratosthenelinear,n)
    test(Eratosthene4,n)