Probleme nombre premiers

Version imprimable

[RESOLU] Probleme nombre premiers

Bonjour à tous, j'essaie d'écrire un petit programme qui affiche les nombres premiers de 1 à 100, j'ai beau relire mon code, la démarche m'a l'air bonne mais quand je l'exécute rien ne se passe :calim2:

voici le code (je commence à parcourir les nombres à partir de 2, en sachant que 1 n'est pas premier):

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void main (String [] args){
 
        int n=100;
 
        for(int i=2; i<n; i++){             
            for (int j=2; j<i; j++){
                int div=0;
                if (i%j==0)              
                {div=div++;}
 
                if (div==1)
                {System.out.println(i);}         
            }
 
            } 
        }

Merci d'avance :P

Salut,

Déjà remplace div = div++; par div++; ou div = div + 1;

Ensuite je te laisse regarder le problème suivant =)

Edit : Penses à la balise code :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void main (String [] args){
 
    int n=100;
 
    for(int i=2; i<n; i++){
        for (int j=2; j<i; j++){
            int div=0;
            if (i%j==0)
                {div++;}
 
            if (div==1)
                {System.out.println(i);}
        }
    }
}

26/11/2009, 18h56
polymorphisme

Les maths sont tes amies

Bonsoir,

tu peux simplifier avec le crible d'Erathostène.

En effet div=div++, c'était un peu spécial :roi:
J'ai modifié un peu le code et quand je le relis, la methode semble bonne mais il m'affiche seulement 2 et 3 :help:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 public static void main (String [] args){
 
        int n=100;
        int div=0;
 
        for(int i=2; i<n; i++){             //on parcourt les nombres i de 2 à 100
            for (int j=2; j<=i; j++){
                if (i%j==0)              // si le nombre est divisible on incrémente div de 1
                {div=div+1;}
            }
                if (div==1)              // si i admet un seul diviseur alors il est premier et on l'affiche
                {System.out.println(i);
                    div=0;}         
 
 
            } 
        } 
    }

27/11/2009, 08h16
Tommy31

Le "div=0" mériterait d'être effectué à chaque itération de la boucle i.

Après, comme dit, ton algo n'est pas optimal.
27/11/2009, 17h31
polymorphisme

Diviser pour régner

Bonjour,

c'est que l'on m'a souvent en dis en info :)

En fait, il y a l'astuce très simple qui consiste à faire ce test uniquement avec des nombres impairs, puisque tu sais déjà que tous les nombres pairs ne sont pas premiers puisque divisibles par 2 :)

Ensuite, la solution est écrite dans la démonstration du crible.
27/11/2009, 20h28
Sawy3r

Merci à tous pour vos réponses, en effet le div=0 devait se répéter à chaque boucle i :mrgreen:

Bonsoir.

Sinon, uniquement lorsque le nombre doit être compris entre 1 et 100 (au delà ça ne marche pas), il suffit de s'assurer que le nombre n'est pas divisible par 2, ni par 3, 5 et 7 (lorsqu'il est plus grand que ces derniers).

Ceci aurait donc suffit à résoudre le problème :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 public static void main (String [] args) { int i = 0; System.out.println ("1\n2\n3\n5\n7"); for (i = 8; i<=100 ; i++) { if (i%2 != 0 && i%3 !=0 && i%5 != 0 && i%7 != 0) { System.out.println (i); } } }
Sinon, au delà de 100, il ne doit pas être divisibles par des multiples de ces premiers nombres premiers cités (2, 3, 5, et 7).

01/12/2009, 16h24
polymorphisme

Quelques rectifications

Bonjour,

Citation:

Sinon, uniquement lorsque le nombre doit être compris entre 1 et 100 (au delà ça ne marche pas), il suffit de s'assurer que le nombre n'est pas divisible par 2, ni par 3, 5 et 7 (lorsqu'il est plus grand que ces derniers).

,

Alors voilà comment cela fonctionne : dans la démonstration du crible, on montre que la recherche des nombres premiers inférieurs à n est équivalente à la recherche des nombres premiers inférieurs à racine carrée de n.

Ainsi, on a sqrt(100)= 10, on recherche donc avec 2, 3, 5 et 7 <= 10.
Si l'on avait eu n=170, on aurait fait une recherche avec 2, 3, 5, 7, 11 et 13

Citation:

Sinon, au delà de 100, il ne doit pas être divisibles par des multiples de ces premiers nombres premiers cités (2, 3, 5, et 7).

C'est une conditions nécessaire, mais loin d'être suffisante, puisqu'on a par exemple 11x11 n'est pas divisible par 2, 3, 5 ou 7 et n'est pas premier.