Excercice nombres premiers
Bonjour,
Je suis actuellement une formation en programmation Java et j'ai un exercice avec lequel je ne parviens pas à m'en sortir.
Voici l'énoncé :
Citation:
Les mathématiciens supposent (Mais cela n'a pas encore été démontré à ce jour ; c'est ce qu'on appelle la « conjecture de Legendre », d'après le mathématicien français du 18e–19e siècle Adrien-Marie Legendre.) que pour tout nombre entier n, il existe au moins un nombre premier compris entre n2 et (n+1)2. C'est ce que nous voulons vérifier à l'aide d'un programme.
Nous allons pour cela utiliser plusieurs sous-tâches (Il existe bien sûr plusieurs autres solutions (d'autres algorithmes), comme par exemple stocker en mémoire les résultats déjà acquis. Nous avons ici pris le parti de ne rien stocker en mémoire, mais de refaire les calculs à chaque fois. Nous vous demandons de respecter cette marche à suivre.) :
savoir si un nombre donné est un nombre premier ;
tester si un nombre entier donné n vérifie la propriété ci-dessus ;
tester tous les nombres entiers compris entre deux bornes.
Pour la première sous-tâche, nous vous demandons d'écrire une fonction estPremier prenant en paramètre un int et retournant un booléen, « vrai » si le nombre fourni en paramètre est un nombre premier et « faux » sinon.
Pour tester si un nombre x est premier, on peut procéder comme suit :
tout nombre inférieur ou égal à 1 n'est pas premier ;
2 est premier ;
tout autre nombre pair n'est pas premier ;
pour tout autre nombre (forcément impair donc), on recherche un diviseur :
faire une boucle de 3 à la racine carrée de ce nombre x (La racine carrée de x s'écrit « Math.sqrt(x) » en Java.) ; si le reste de la division entière de x par le nombre de la boucle est nul, alors x n'est pas premier ;
si à la fin de la boucle, tous les restes étaient non nuls, alors x est premier ;
pour rappel, le reste de la division entière de x par y s'écrit « x % y » en Java.
Afin de tester si votre procédure est correcte, nous vous demandons de plus d'écrire une fonction testPremiers prenant deux entiers en paramètres et testant chaque entier compris entre ces deux bornes pour voir s'il est premier. Cette fonction devra écrire à l'écran la liste des nombres premiers trouvés en respectant strictement le format donné dans les exemples de déroulement fournis plus loin.
Pour tester si un nombre entier donné n vérifie la propriété de la conjecture de Legendre, nous vous demandons d'écrire une fonction legendre qui prend en paramètre un int n et retourne un int. Cette fonction testera tous les nombres compris entre n*n+1 et (n+1)*(n+1)-1 et s'arrêtera au premier nombre premier rencontré, qu'elle retournera. Si, par contre, aucun nombre premier n'a été trouvé entre ces deux bornes, la fonction retournera 0.
Enfin, la dernière fonction à fournir s'appelle testLegendre. Elle ne prend aucun paramètre et ne retourne rien. Elle commence par demander à l'utilisateur d'entrer un nombre en respectant strictement le format donné dans les exemples de déroulement fournis plus loin. Tant que le nombre entré par l'utilisateur est inférieur ou égal à 0, la fonction redemande un nombre. Une fois ce premier nombre entré, elle demande un second nombre, qui doit être supérieur ou égal au premier nombre entré (voir exemples de déroulement plus bas).
Une fois que deux valeurs valides ont été fournies, la fonction effectue enfin le test de la conjecture de Legendre sur tous les nombres compris entre les deux nombres saisis. Si la conjecture est vérifiée, cette procédure affiche le nombre testé suivi de « : » suivi du premier nombre premier trouvé (voir exemples de déroulement plus bas). Sinon, si jamais le nombre testé ne vérifie pas la conjecture de Legendre, alors le programme doit afficher « PAS TROUVÉ ! » (Et à vous la célébrité!).
Et voici mon code :
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
74
75
76
| import java.util.Scanner;
class Legendre {
private final static Scanner clavier = new Scanner(System.in);
public static void main(String[] args) {
testPremiers(0, 100);
System.out.println();
testLegendre();
}
/*****************************************************
* Compléter le code à partir d'ici
*****************************************************/
private static boolean testLegendre(int a) {
boolean respuesta = true;
double raiz = Math.sqrt(a);
if(a < 2){
return false;
} else if(a == 2){
return true;
} else{
if(a % 2 == 0){
respuesta = false;
} else {
int i = 3;
while(i <= raiz){
if(a % i == 0){
respuesta = false;
break;
}
i++;
}
}
}
return respuesta;
}
static void testPremiers(int b, int c){
System.out.print("Premiers entre " + b);
System.out.print(" et ");
System.out.println(c + " :");
for (int i = b; i <= c; ++i){
if(testLegendre(i)){
System.out.print(i + ", ");
}
}
System.out.println("");
System.out.println("");
System.out.print("Tester la conjecture de Legendre entre : ");
System.out.print("et : ");
System.out.print("PAS TROUVÉ !");
/*******************************************
* Ne rien modifier après cette ligne.
*******************************************/
}
} |
Quelqu'un saurait-il me guider un peu ?
Merci d'avance pour votre aide.
