# -*- coding:utf-8 -*-

__projet__ = "correction_examen_semestre_6_AF1"
__nom_fichier__ = "goldbach"
__author__ = "Christine Fay-Varnier"
__date__ = "mai 2025"

from time import time

"""
La conjecture de Goldbach affirme que tout nombre PAIR supérieur ou égal à 4 est la somme de deux nombres 
"""


def goldbach(x, lpremiers):
    """

    @param x:           nombre pair
    @param lpremiers:   liste de nombres premiers
    @return:            True si la conjecture est vérifiée pour x
    """
    if x < 4 or x % 2 == 1:
        return False

    for p in lpremiers:
        # si x = p + q, alors q = x - p
        # et pour vérifier la conjecture de Goldbach, il suffit de vérifier que x-p est un nombre premier
        if x-p in lpremiers:
            return p, x-p

    return False

def goldbach_V2(x, lpremiers):
    """

    @param x:           nombre pair
    @param lpremiers:   liste de nombres premiers inférieurs ou égaux à x
    @return:            le couple de nombres premiers dont la somme est égale à x si la conjecture de Golbach est vérifiée pour x
                        False sinon
    """
    if x < 4 or x % 2 == 1:
        return False

    for p1 in lpremiers:
        # je parcours la liste des nombres premiers pour trouver une décomposition possible
        for p2 in lpremiers:
            if p1 + p2 == x:
                return p1, p2

    return False


def goldbach_V3(x, lpremiers):
    """

    @param x:           nombre pair
    @param lpremiers:   liste de nombres premiers inférieurs ou égaux à x
    @return:            le couple de nombres premiers dont la somme est égale à x si la conjecture de Golbach est vérifiée pour x
                        False sinon
    """
    if x < 4 or x % 2 == 1:
        return False

    for i in range(len(lpremiers)):
        # on tente d'optimiser en ne regardant que les nombres qui sont après le rang i
        # mais quand on fait les essais, on peut s'apercevoir que l'optimisation n'apporte rien
        # voir diminue l'efficacité de la fonction, ce qui est certainement dû à l'accès aux valeurs
        # des éléments de la liste avec les indices
        for j in range(i, len(lpremiers)):
            if lpremiers[i] + lpremiers[j] == x:
                return lpremiers[i], lpremiers[j]

    return False


def listeGoldbach(n, lpremiers):
    """
    On suppose que la conjecture est vérifiée et que la fonction goldbach retourne toujours un couple (ne retourne jamais False).
    Écrire une fonction listeGoldbach qui :
    reçoit en paramètre une valeur n et la liste des nombres premiers inférieurs ou égaux à n
    retourne la liste des couples correspondant à la décomposition de Goldbach pour les nombres pairs de 4 à n exclu

    @param n:           nombre maximum à traiter
    @param lpremiers:   liste des premiers
    @return:            liste des couples correspondant à la décomposition de Goldbach pour les nombres pairs de 4 à n exclu
    """
    lcouples = []
    for v in range(4, n, 2):
        # peut s'écrire avec un while mais 'est beaucoup moins efficace
        # on peut aussi tester if v%2==0 mais c'est moins rapide
            p, q = goldbach(v, lpremiers)
            lcouples.append((p, q))     # Attention à bien ajouter un couple à la liste

    return lcouples

def listeGoldbach_V2(n, lpremiers):
    """
    On suppose que la conjecture est vérifiée et que la fonction goldbach retourne toujours un couple (ne retourne jamais False).
    Écrire une fonction listeGoldbach qui :
    reçoit en paramètre une valeur n et la liste des nombres premiers inférieurs ou égaux à n
    retourne la liste des couples correspondant à la décomposition de Goldbach pour les nombres pairs de 4 à n exclu

    @param n:           nombre maximum à traiter
    @param lpremiers:   liste des premiers
    @return:            liste des couples correspondant à la décomposition de Goldbach pour les nombres pairs de 4 à n exclu
    """
    lcouples = []
    for v in range(4, n):
       # version un peu moins rapide que la précédente
        if v%2==0:
            p, q = goldbach(v, lpremiers)
            lcouples.append((p, q))     # Attention à bien ajouter un couple à la liste

    return lcouples

def listeGoldbach_V3(n, lpremiers):
    """
    On suppose que la conjecture est vérifiée et que la fonction goldbach retourne toujours un couple (ne retourne jamais False).
    Écrire une fonction listeGoldbach qui :
    reçoit en paramètre une valeur n et la liste des nombres premiers inférieurs ou égaux à n
    retourne la liste des couples correspondant à la décomposition de Goldbach pour les nombres pairs de 4 à n exclu

    @param n:           nombre maximum à traiter
    @param lpremiers:   liste des premiers
    @return:            liste des couples correspondant à la décomposition de Goldbach pour les nombres pairs de 4 à n exclu
    """

    lcouples = []
    v = 4
    while v<=n:
        # version encore moins rapide que les deux précédentes
        if v%2==0:
            p, q = goldbach(v, lpremiers)
            lcouples.append((p, q))     # Attention à bien ajouter un couple à la liste
            v += 2

    return lcouples

def densiteJumeaux(n, lpremiers):
    """
    deux nombres premiers jumeaux sont deux nombres premiers qui ne diffèrent que de 2 :
    Exemples : 3 et 5, 5 et 7, 17 et 19
    Écrire une fonction densiteJumeaux qui :
    •	reçoit en paramètre une valeur n et la liste des nombres premiers inférieurs ou égaux à n
    •	récupère la liste des couples de nombres premiers obtenue par la fonction écrite dans la question 2) pour la valeur n
    •	retourne le nombre de couples « jumeaux » dans la liste obtenue

    @param n:           nombre maximum à traiter
    @param lpremiers:   liste de nombres premiers
    @return:            retourne le nombre de couples « jumeaux » dans la liste des couples de nombres premiers pour la valeur n
                        deux nombres premiers jumeaux sont deux nombres premiers qui ne diffèrent que de 2
    """
    lcouples = listeGoldbach(n, lpremiers)  # on récupère la liste de couples permettant de décomposer tous les

    n = 0
    for p, q in lcouples:
        if q == p+2:    # on teste la différence entre les deux éléments de la liste
            n += 1

    return n

def densiteJumeaux_V2(n, lpremiers):
    """
    deux nombres premiers jumeaux sont deux nombres premiers qui ne diffèrent que de 2 :
    Exemples : 3 et 5, 5 et 7, 17 et 19
    Écrire une fonction densiteJumeaux qui :
    •	reçoit en paramètre une valeur n et la liste des nombres premiers inférieurs ou égaux à n
    •	récupère la liste des couples de nombres premiers obtenue par la fonction écrite dans la question 2) pour la valeur n
    •	retourne le nombre de couples « jumeaux » dans la liste obtenue

    @param n:           nombre maximum à traiter
    @param lpremiers:   liste de nombres premiers
    @return:            retourne le nombre de couples « jumeaux » dans la liste des couples de nombres premiers pour la valeur n
                        deux nombres premiers jumeaux sont deux nombres premiers qui ne diffèrent que de 2
    """
    lcouples = listeGoldbach(n, lpremiers)  # on récupère la liste de couples permettant de décomposer tous les

    n = 0
    for couple in lcouples:
        p, q = couple
        if q == p+2:    # on teste la différence entre les deux éléments de la liste
            n += 1

    return n

def densiteJumeaux_V3(n, lpremiers):
    """
    deux nombres premiers jumeaux sont deux nombres premiers qui ne diffèrent que de 2 :
    Exemples : 3 et 5, 5 et 7, 17 et 19
    Écrire une fonction densiteJumeaux qui :
    •	reçoit en paramètre une valeur n et la liste des nombres premiers inférieurs ou égaux à n
    •	récupère la liste des couples de nombres premiers obtenue par la fonction écrite dans la question 2) pour la valeur n
    •	retourne le nombre de couples « jumeaux » dans la liste obtenue

    @param n:           nombre maximum à traiter
    @param lpremiers:   liste de nombres premiers
    @return:            retourne le nombre de couples « jumeaux » dans la liste des couples de nombres premiers pour la valeur n
                        deux nombres premiers jumeaux sont deux nombres premiers qui ne diffèrent que de 2
    """
    lcouples = listeGoldbach(n, lpremiers)  # on récupère la liste de couples permettant de décomposer tous les

    n = 0
    for couple in lcouples:
        if couple[1] == couple[0] + 2:    # on teste la différence entre les deux éléments de la liste
            n += 1

    return n

if __name__ == '__main__':
    lpremiers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

    # la 1ère version est 3 fois plus rapide que la seconde qui contrairement à ce qu'on pourrait penser est plus rapide
    # que la 3ème version, ce qui est certainement dû à l'utilisation des indices pour accéder aux élément dans la liste

    # print(goldbach(4, lpremiers))
    # print(goldbach(50, lpremiers))
    # print(goldbach(112, lpremiers))
    #
    # print(goldbach_V2(4, lpremiers))
    # print(goldbach_V2(50, lpremiers))
    # print(goldbach_V2(112, lpremiers))
    #
    # print(goldbach_V3(4, lpremiers))
    # print(goldbach_V3(50, lpremiers))
    # print(goldbach_V3(112, lpremiers))

    # n = 20
    #
    # print(listeGoldbach(n, lpremiers))
    # print(listeGoldbach_V2(n, lpremiers))
    # print(listeGoldbach_V3(n, lpremiers))

    n = 100
    print(densiteJumeaux(n, lpremiers))
    print(densiteJumeaux_V2(n, lpremiers))
    print(densiteJumeaux_V3(n, lpremiers))