Conjecture de goldbach

Version imprimable

16/01/2016, 18h07
magyy

Conjecture de goldbach

Bonjour,
je bloque sur l'écriture d'un programme qui doit vérifier sur des entrées la conjecture de Goldbach, à savoir tout nombre pair est décomposable en la somme de deux nombres premiers.
Merci d'avance!
16/01/2016, 18h31
Matt_Houston

Qu'as-tu à proposer ?
17/01/2016, 08h38
ternel

Sur quoi bloques-tu concrètement?

L'algorithme ou sa transcription en code?
17/01/2016, 17h03
magyy

Je bloque sur l'écriture de l'algorithme
17/01/2016, 18h50
dalfab
Bonjour,

Citation:

Envoyé par magyy

Je bloque sur l'écriture de l'algorithme

Tu as donc déjà fait le raisonnement suivant :
Tous nombre pair est somme de :
- soit deux nombres pairs
- soit deux nombres impairs
Le seul pair premier est le 2. S'il y a deux pairs, il s'agit de 2+2 : Le cas du seul nombre 4 est résolu.
On s'intéresse donc aux nombres pairs à partir de 6, ils sont sensés être sommes de deux nombres impairs. Il faudrait essayer toutes les combinaisons.
Pour un N donné, parcourir tous les couples impairs potentiellement premiers.
Par exemple pour N = 14, on devrait avoir les couples (3;11) (5;9) (7;7) (9;5) et (11;3).
Et ensuite il reste à vérifier que pour au moins un des couples, les deux nombres sont premiers.

Maintenant, en terme informatique, je pressens les fonctions :
- ParcourirLesNombresPairsAPartirDe6 ou DemanderLaSaisieDUnNombrePairSuperieurA6
- ParcourirLesPairesImpairesDUnNombre
- LeNombreEstTIlPremier
Essayer de mettre en forme ces fonctions et d'en écrire le corps pourrait être une bonne base selon moi.
Il faut nous proposer des choses, et nous pourrons t'aider.
18/01/2016, 10h02
stendhal666

Il y a en fait deux problèmes en 1:
- la génération des nombres premiers, ou la vérification qu'un nombre est premier
- la décomposition d'un nombre pair en deux nombres premiers

L'exercice ne mentionne pas une borne pour le test, c'est-à-dire le plus grand entier à tester? Mettons une borne B, je conseillerais:
- générer les nombres premiers jusqu'à B - 3
- pour chaque nombre pair P entre 6 et B, on parcourt la liste des nombres premiers: si (P - premier_i) appartient à liste des nombres pairs, la conjecture est vérifiée, on passe au nombre P suivant.

Pour la génération des nombres premiers, tu peux utiliser le crible d'Eratosthène, qui n'est pas difficile à implémenter: https://fr.wikipedia.org/wiki/Crible...atosth%C3%A8ne
Pour la suite, il ne s'agit que d'une simple boucle...

voilà ce que j'ai pu coder à partir des explications et ça marche!

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
 
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
bool EstPremier(int p)
{
    int i,d=0;
    bool b;
 
    for(i=1;i<=p;i++)
    {
        if(p%i==0)
        {
            d=d+1;
        }
    }
    if(d==2)
    {
        b=true;
    }
    else{
        b=false;
    }
    return b;
}
 
 
int main()
{  int x,i,j,k=0,s;
   int t[2];
   bool m,q;
    do{
    printf("Veuillez saisir un nombre pair \n");
    scanf("%d",&x);
    }while(x%2!=0);
    if(x==4)
    {
        printf("La conjecture de Goldbach est verifie : 4 =2+2");
    }
    else
    {
        if(x>=6)
 
        {
            printf("La conjecture de Goldbach est verifie\n");
            for(i=1;i<x;i=i+2)
            {
                    for(j=1;j<x;j=j+2)
                {
                    s=i+j;
                    if(s==x)
                    {
                        t[k]=i;
                        t[k+1]=j;
 
                        m=EstPremier(t[k]);
                        q=EstPremier(t[k+1]);
                        if((m==true)&&(q==true))
                        {
 
                        printf("%d = %d+%d \n",x,t[k],t[k+1]);
                        }
                    }
                }
 
            }
 
        }
    }
 
    return 0;
}

Merci à tous de m'avoir aidé!!