def factorielle(n):
    """Renvoie la factorielle de n."""
    f=1
    for k in range(1,n+1):
        f=f*k
    return f


## Exercice 1

def estpair(n):
    return n%2==0

print(estpair(7))
print(estpair(42))
print(estpair(-8))


def intsqrt(n):
    a=0
    while a**2<=n:
        a+=1
    return a-1

print(intsqrt(50))
print(intsqrt(81))
print(intsqrt(1000))


def Occurrences(a,L):
    n=0
    for elt in L:
        if elt==a:
            n+=1
    return n

print(Occurrences(2,[1,2,3,4]))
print(Occurrences(1,[1,1,2,3,5,8]))
print(Occurrences(15,[1,4,9,16,25,36]))


def maxi(L):
    m=L[0]
    for i in range(len(L)):
        if L[i]>m:
            m=L[i]
    return m

print(maxi([16,1,36,25,9,4]))
print(maxi([2,2,2,2,2,2]))
print(maxi([1,1,2,3,5,8]))


## Exercice 2

def CoefBino(n,k):
    """Calcule (k parmi n)."""
    if 0<=k and k<=n:
        return factorielle(n)//factorielle(k)//factorielle(n-k)
    return 0

for [n,k] in [[0,0],[3,1],[6,9],[50,13],[10000,9997]]:
    print(n,k,CoefBino(n,k))
for k in range(5):
    print(CoefBino(4,k))

def LigneSuivante(L):
    M=[L[0]]
    for k in range(len(L)-1):
        M.append(L[k]+L[k+1])
    M.append(L[-1])
    return M

print(LigneSuivante([3,5,-1,0,7]))


N=int(input("Combien de lignes voulez-vous ? "))

L=[1]
print(L)
for n in range(N):
    L=LigneSuivante(L)
    print(L)

## Exercice 3

from math import sqrt

def est_premier(n):
    """Teste si n est premier."""
    if n<2:
        return False
    for k in range(2,int(sqrt(n))+1):
        if n%k==0:
            return False
    return True

for i in range(21):
    if est_premier(i):
        print(i,end=' ')
print()

for i in range(1000):
    if est_premier(i):
        n+=1
print("Nombre de nombres premiers inférieurs à 1000 :",n)

depart=10**10
k=depart
while not est_premier(k):
    k+=1
print(k,"est le premier nombre premier après",depart)

## Exercice 4

from math import sqrt

def Crible(N):
    """Construit le crible D'Eratosthène."""
    # Création du crible :
    C=[False]*2+(N-2)*[True]
    # Parcours du crible :
    for n in range(2,int(sqrt(N))+1):
        if C[n]:
            for k in range(n**2,N,n):
                C[k]=False
    return C

C1=Crible(21)
for n in range(21):
    if C1[n]:
        print(n,end=' ')
print()


C1=Crible(1000)

n=0
for b in C1:
    if b:
        n+=1

print("Nombre de nombres premiers inférieurs à 1000 :",n)

## Exercice 5

from time import process_time

N=100000

t1=process_time()
C1=[]
for k in range(N+1):
    C1=C1+[est_premier(k)]
t2=process_time()

t3=process_time()
C2=Crible(N)
t4=process_time()

print("Temps pour l'algorithme naïf : ",t2-t1)
print("Temps pour le crible d'Eratosthène :",t4-t3)

## Exercice 6

def Diviseurs(n):
    """Renvoie la liste des diviseurs de n autres que lui-même."""
    LD=[]
    for k in range(1,n):
        if n%k==0:
            LD.append(k)
    return LD

# for k in [1,2,3,4,12,28,29]:
#   print(Diviseurs(k))

def Somme(L):
    """Calcule la somme des nombres de la liste L."""
    S=0
    for a in L:
        S+=a
    return S

def Parfait(n):
    """Teste si n est parfait."""
    return Somme(Diviseurs(n))==n

lim=10**4
for n in range(1,lim+1):
    if Parfait(n):
        print(n,"est parfait. ")

for n in range(1,lim+1):
    m=Somme(Diviseurs(n))
    if m>n and n==Somme(Diviseurs(m)):
        print(n,'et',m,'sont amis.')

## Exercice 7

N=2**10
C=Crible(N)
c=0
for k in range(1,N-2,2): # Inutile de tester les pairs
    if C[k] and C[k+2]:
        print("(",k,",",k+2,")",sep="")
        c+=1
print("Il existe ",c," couples de nombres premiers jumeaux inférieurs à ",N,".",sep="")

## Exercice 8

N=2**10
C=Crible(N)

Conjecture=True
affichage=True # contrôle l'affichage des sommes
for n in range(4,N,2): # on parcourt les entiers pairs
    k=2
    while not(C[k] and C[n-k]) and k<=n//2:
        k+=1
    if C[k] and C[n-k]:
        if affichage:
            print(n,"=",k,"+",n-k)
    else:
        print("La conjecture est fausse :",n,"ne la vérifie pas.")
        Conjecture=False
if Conjecture:
    print("La conjecture est vraie au moins jusqu'à",N)