Nombre premiers et calculer la racine carrée d'un nombre

**Roud9** · 18/09/2010, 05h02

Bonjour,

C'est la première fois que je poste sur ce site, donc je ne sais pas si c'est vraiment la bonne catégorie. J'essaie d'écrire un petit programme java qui détermine si un nombre est premier ou non, ça donne ça:

if (nombreEntré % 2 != 0)
System.out.println(nombreEntré +" est un nombre premier");
else if(nombreEntré % 2 == 0 && nombreEntré != 2)
System.out.println(nombreEntré +" n'est pas un nombre premier");

mais si je rentre 51 (qui n'est pas un nombre premier) il me dit qu'il est premier parce qu'il est impair. Ma question est de quel façon faut-il modifier le programme pour qu'il détecte les nombre impairs composés comme étant non premiers?

Et je cherche à exprimer la racine carrée d'un nombre, mais sans math.sqrt(), plutôt avec des boucle if...else ou while. y'a t'il un moyen?

Merci d'avance

**akrom** · 18/09/2010, 07h23

Voila une fonction pour calculé une racine carre.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
public Double racineCarre(Double nombre){
        double resultat = 0 ;
        double rc2;
        int i=0;
        double rc1=1;
 
        while(i<100){
            resultat=0.5*(rc1+(nombre/rc1));
            rc1=resultat;
            i++;
        }
        return resultat;
    }

Plus le nombre de tour de boucle est important plus le résultat sera précis

**tchize_** · 18/09/2010, 10h57

c'est plutot dans la section algorithme que tu devrais aller. Savoir si un nombre est premier ou pas, c'est un algorithme récursif, qui basiquement va parcourir tous les nombres de 1 à SQRT(N) pour voir si ils divisent N. Quand à la racine carrée 'à la main', il existe plus algorithme, faire une recherche sur le net. Pareil d'ailleurs pour l'algorithme des nombres premiers.

**Ivelios** · 18/09/2010, 13h07

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
	public boolean isPremier(int n) {
		boolean isPremier = true;
		if (n < 0) {
			isPremier = false;
		} else if (n != 0 && n != 1) {
			for (int i = 2; i <= n/2; i++) {
				if (n != i && n % i == 0) {
					isPremier = false;
					break;
				}
			}
		}
		return isPremier;
	}

premier lien google

avec "nombre premier java"

**tchize_** · 18/09/2010, 13h25

comme je l'ai dit n/2 sert à rien, on s'arrête à la racine carré :p

**micuthana** · 18/09/2010, 16h02

et juste pour info : le %2 te dira si le nombre est impair ou non et non si il est premier.

**droggo** · 18/09/2010, 16h13

Sia,

Comme si souvent, l'algorithme est une simple traduction dans le langage visé de ce que tu dois faire à la main pour décider.

Pour les puristes en math : on parle ici d'algorithme basique, ce qui est attendu pour un tel exercice de cours.

**Roud9** · 19/09/2010, 02h00

Merci pour vos réponses. Pour les racines carrées, ça ressemble à ceci:

0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4...
on voit qu'il y a des répétitions et que
0 se répète 1 fois
1 se répète 3 fois
2 se répète 5 fois
3 se répète 7 fois

J'ai juste trouvé que les nombres se répète 2n+1 fois , mais je ne sais pas si ça va m'aider

**tchize_** · 19/09/2010, 02h16

on l'a dit, une simple recherche en ligne et tu trouveras des algorithmes de base pour le faire.
des plus simples
http://fr.wikipedia.org/wiki/Méthode_de_Héron

aux plus tordues et limitées

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
	inline float sqrt(float number) {
    long i;
    float x, y;
    const float f = 1.5F;
 
    x = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;
    i  = 0x5f3759df - ( i >> 1 );
    y  = * ( float * ) &i;
    y  = y * ( f - ( x * y * y ) );
    y  = y * ( f - ( x * y * y ) ); // si on veut plus de précision
    return number * y;
}

**Roud9** · 20/09/2010, 06h29

Merci, j'ai trouvé ce que je je cherchais. J'essaie de faire des bouche for des while, mais cela ne fonctionne pas

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
if (nombreEntré < 2)
                {
                    premier = false;
                }
 
                for (int i = 2; i*i <= nombreEntré; i++)
 
 
                if (nombreEntré % i == 0)
                    {
                        premier = false;
                    }
 
 
                    if (premier)
                    {
                        System.out.println(nombreEntré + " est un nombre premier");
                    }
                else
                {
                    System.out.println(nombreEntré + " n'est pas un nombre premier");
                }

le for deviendrait

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
int i = 2
while(i * i <= nombreEntré)
i = i + 1

selon moi, mais ça ne fonctionne pas

**Ivelios** · 20/09/2010, 07h26

Dans la boucle for : tu fait TOUT LE TEMPS des System.out.println ...
Affiche le résultat seulement à la fin :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
                if (nombreEntré < 2)
                {
                    premier = false;
                }else{//Pas la peine d'entrée dans la boucle for
                  int indice = i*i;//Utiliser un entier fixe. rmq : i*i dans la boucle for sera tous les temps recalculer et augmentera tous le temps
                for (int i = 2; indice <= nombreEntré; i++){
 
 
                if (nombreEntré % i == 0)
                    {
                        premier = false;
                        break; // Pas la peine de continuer dans la boucle
                    }
 
                }}
                if(premier) System.out.println(nombreEntré +" est premier");
                else System.out.println(nombreEntré +" n'est pas premier");

**tchize_** · 20/09/2010, 08h39

Envoyé par Ivelios

Dans la boucle for : tu fait TOUT LE TEMPS des System.out.println ...

Désolé mais non, son for ne contient que le if, ce qui est correct.

Par contre, j'aurais tendance à sortir de la boucle dès que premier==false pour aller plus vite, mais ce n'est pas catastrophique pour débuter.

Pourquoi tu veux changer ton for en while?

**Ivelios** · 20/09/2010, 09h36

Tu as raison, je n'avais pas remarqué qu'il n'avait pas mis les acolades au for

.

**Roud9** · 20/09/2010, 14h30

Est-ce qu'il ya moyen? sinon je vais je laisser comme ça

**akrom** · 20/09/2010, 14h51

il faut remplacer :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
for (int i = 2; i*i <= nombreEntré; i++)
 
 
                if (nombreEntré % i == 0)
                    {
                        premier = false;
                    }

par :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
int i = 2
while(i * i <= nombreEntré){
if (nombreEntré % i == 0)
                    {
                        premier = false;
                    }
i = i + 1;
}

Mais je n'en vois pas l'utilité.

**Roud9** · 20/09/2010, 23h25

Merci, je voulais juste savoir si ça se faisait (parce que l'on parle de deux boucles) et si oui comment

**Ivelios** · 20/09/2010, 23h55

je voulais juste savoir si ça se faisait (parce que l'on parle de deux boucles)

while et for c'est la même chose... mais en différent

Lors de la création de l'univers il y avait le while. Mais les astres voulait quelque chose de plus rapide à écrire, de plus compacte. Et le for naquit des entrailles du while.

**Jimmy_** · 21/09/2010, 16h52

Diviser le nombre par deux ce n'est pas la bonne méthode, ce n'est même pas une version naïve. L'algorithme de base pour détecter si un nombre est premier est le crible d'Eratoshtène. Pour des nombres pas trop grand c'est largement suffisant.

Bon article avec animation : http://fr.wikipedia.org/wiki/Crible_...atosth%C3%A8ne

Après on trouve tout un tas d'algorithmes très compliqués pour aller plus loin, car les propriétés des nombres premiers sont utilisés en cryptanalyse entre autre.