Problème mathématique avec les nombres

**ramirami** · 07/02/2007, 22h42

bonjour a vous tous. J'essaye de develloper une application JAVA qui fera ce qui suit :

1-Demander a l'usager de rentrer un nombre entier
2-Determiner si le nombre est divisible (C'est a dire qu'on peut le diviser par lui même et par 1 seulement)
3- Si le nombre n'est pas divisible c'est a dire si c'est un nombre composé qui peut être divisé par plusieurs facteurs il faut calculer les facteurs.

Par exemple : 53 est un nombre divisible

Par exemple : 18 est un nombre composé qui a les facteurs suivants :
1 18
2 9
3 6

Avez-vous des idées pour développer cette application????

Merci de votre aide

**mavina** · 07/02/2007, 23h56

Bonjour,

En gros, ce que tu souhaites, c'est savoir si un nombre N est premier ou pas.
Un algorithme naïf serait de vérifier tous les diviseurs de 2 à N-1, mais ce serait beaucoup trop long. Mes souvenirs de terminale me disent que de 1 à racine(n) est suffisant. Enfin, on peut élaguer l'algorithme apres avoir vérifié par 2, on arrette les multiples de deux, par 3 les multiples de 3, par 5 les ...
On a déja bien élagué avec juste ces 3 nombres

Voilà, à toi de jouer

Cordialement

Fred

**ramirami** · 08/02/2007, 00h08

Merci pour ta réponse. Mais ce n'est pas évident. Ce qui me rend la vie difficile c'est comment commencer cet algorithme????. C'est le début qui est dûr. Je continue a faire de la recherche dans des livres JAVA et sur internet. Mais pour le moment je n'ai pas toujours la réponse.

Toute aide est fortement apprécié. merci

**jobherzt** · 08/02/2007, 00h18

la factorisation des nombres est un domaine extremement vaste, et il existe des dizaine d'algorithme d'efficacité et de difficultés differentes. la solution que te donne mavina est simple sans etre naive et elle est a priori le meilleur compromis si tes nombres ne depassent pas une dizaine de chiffres. je ne vois donc pas pourquoi tu affirmes ne pas avoir de reponses

on peut difficilement faire plus simple a implementer....

**ramirami** · 08/02/2007, 00h31

Salut les amis. J'aimerais vous rappeler que je suis débutant. Des choses qui pourront vous paraître faciles me prennent énormément de temps. Cet algorithme pour vous il est simple mais pour moi c'est u vrai casse tête.
J'essaye toujours sans résultat........A suivre

**jobherzt** · 08/02/2007, 00h36

d'abord, tu n'a pas precisé que tu etais debutant... ensuite, debutant en quoi ? est l'algorithme qui te pose probleme ? ou le fait de le passer en java ? as tu compris "sur le papier" la methode de mavina ?

**ramirami** · 08/02/2007, 00h46

jobhertz merci pour ta réponse. Au fait je comprends un peu le concept mais c'est passer a JAVA qui me cause problème. Par exemple le nombre 18 a plusieurs facteurs par lesquels on peut le diviser : 1, 2, 3, 6, 9, 18
Comment écrire en JAVA un algorithme qui me permettra de determiner ces facteurs ......C'est trop dûr je trouve. J'ai besoin d'un début de code,,,,
merci

**mavina** · 08/02/2007, 00h48

Allez, juste pour que tu comprennes, je vais tenter le pseudo langage :

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
 
fonction estPremier ( Entier N)
  si N = 1
    retourner vrai
  fin si
  si N modulo 2 = 0 || N modulo 3 = 0 || N modulo 5 = 0
    retourner faux
  fin si
  pour i allant de 2 à racine (N), i n étant pas un multiple de 2, 3 ou 5
    si N modulo i = 0
      retourner faux
    fin si
  fin pour
  retourner vrai
fin fonction

Je pense qu'il est correct

Cordialement

Fred

**jobherzt** · 08/02/2007, 01h00

Envoyé par ramirami

jobhertz merci pour ta réponse. Au fait je comprends un peu le concept mais c'est passer a JAVA qui me cause problème. Par exemple le nombre 18 a plusieurs facteurs par lesquels on peut le diviser : 1, 2, 3, 6, 9, 18
Comment écrire en JAVA un algorithme qui me permettra de determiner ces facteurs ......C'est trop dûr je trouve. J'ai besoin d'un début de code,,,,
merci

au vu de cette reponse je ne suis pas sur que tu aies compris... si on te donne un bout de code, tu es sur que tu sauras continuer ? peut etre vaut il mieux commencer par ecrire de maniere detaillée la methode qu'on te propose.

**ramirami** · 08/02/2007, 01h17

oui je crois que si vous me donnez le BON CODE au début je serais en mesure de continuer ...............faisons un essai .merci beaucoup

**jobherzt** · 08/02/2007, 01h48

comment feras tu pour continuer si tu n'as pas compris comment ca marche

si tu arrives a ecrire en "francais" la procedure detaillée pour factoriser un nombre, je pense qu'on te donnera un bout de code...

**iohack** · 08/02/2007, 02h26

je pense surtout que c'est un étudiant qui a séché pas mal de cours et qui voudrait qu'on lui fasse son exercice à sa place...
Il a l'air de vraiment vouloir le code plutot que l'explication...

**ramirami** · 08/02/2007, 03h21

iohack....Ta reponse n'est pas sympat du tout. Tu m'attaques gratuitement. Si tu ne veux pas aider la meilleure chose a faire est de se TAIRE.

Pour ton info je n'ai jamais seche de cours dans ma vie. Ca fait 2 jours que je bosse sur ce probleme et je vais continuer d'ailleurs.

Juste arrete tes agressions gratuites .................................

**sricard** · 08/02/2007, 08h33

Salut.

Une idée est de calculer les nombres permiers jusqu'à 10000000.
Je te passe un bout de code :

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
23
24
25
26
27
28
29
30
31
32
33
34
35
 
 
import java.io.*;
 
public class NombresPremiers
{
        public static void main (String[] args)
        {
                int[] P = new int[10000000]; // création d'un tableau                 P[0]=2; // le premier nombre premier est 2
                int lg = 1; // nombre de nombre premier trouvé.
                int i=3; // premier nombre qui va être testé.
 
                for(int j=0;j<lg;j++)
                {
                        if((i%P[j])==0) // si le nombre testé est multiple d'un nombre premier.
                        {
                                j=0; // réinitialisation du compteur
                                i = i+2; // pour un nouveau nombre (on exclu les pairs maintenant).
                        }
                        else    
                        {
                                while(P[j]>Math.sqrt(i)) // si le nombre premier testeur est supérieur au carré du nombre testé, alors il est prémier.
                                {
                                        P[lg] = i; // enregistrement du nb premier dans le tableau.
                                        System.out.print(P[lg]); 
                                        System.out.print(" nombre premier Numero : ");
                                        System.out.println(lg);
                                        lg++; // incrémentation du nombre de premier.
                                        j=0; // réinitialisation du compteur
                                        i=i+2; // pour un nouveau nombre..
                                }
                        }
                }
        }       
}

Ensuite, tu rentres le nombre désiré et tu regardes s'il y est.
S'il n'y est pas, tu regardes s'il est divisible par 2 ou 3 ou.... 9.
Et je pense que la suite est simple.

PS : il se peut que tu dois faire ton code rapidement, mais je pense qu'il serait plus interessant pour toi de comprendre certains algorithmes ( Knuth,Eratosthène,...) et d'ensuite de t'attaquer à le coder seul en JAVA.
C'est la manière la plus efficace de progresser.

Bon courage.

**anoukhan** · 08/02/2007, 10h12

En fait, il existe des algorithmes assez efficaces pour tester la primalité d'un nombre mais ils sont probabilistes: un tel algorithme peut dire qu'un nombre composite est premier avec une certaine probabilité de 2^(-c) ou tu peux adapter ton c.

Si cette méthode te convient et que tu as des nombres assez gros tu peux faire:

Code :

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

1
2
3
4
5
6
7
8
9
 
public boolean isPrime(int p){
  BigInteger i = BigInteger.valueOf(p);
 
  //choisis c
  int c = 100;
 
  return i.isProbablePrime(c);
}

**jobherzt** · 08/02/2007, 14h10

sricard : je ne suis pas sur que ta methode soit tres efficace :-)

anoukhan : n'oublie pas qu'il veut aussi factoriser le nombre.

ramirami : a tu essayé d'ecrire "en francais" la lethode que tu emploierais pour factoriser un nombre, en te basant sur les conseils d'aviva ? tu comprends qu'on ne peut pas travailler a ta place..

**mavina** · 08/02/2007, 21h07

Coucou,

Obtenir tous les facteurs d'un nombre, de façon naive, c'est vérifier que le reste de la division de chaque nombre entre 1 et n est égal à 0.
En java, celà est possible par l'utilisation du modulo (opérateur %).

L'algorithme donnerait :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
	public List<Integer> getDiviseurs (int n)
	{
	  List <Integer>result=new ArrayList<Integer>();
	  for(int i=1;i<=n;i++)
	  {
	  	if(n%i==0)
	    	result.add(i);
	  }
	  return result;
	}

C'est un algorithme plutôt sommaire... A améliorer.

cordialement

Fred

**anoukhan** · 08/02/2007, 22h28

En tout cas ça dépend grandement de la taille de tes nombres. Pour des nombre petits tu peux essayer le modulo mais si ton nombre est grand alors il faudra regarder plutot en théorie des nombres et tous les algo dispo (pollar-rho, baby step giant step...)

**mavina** · 08/02/2007, 23h04

Salut,

Après tests sur mon centrino 1.7ghz, voici les resultats :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
N               Temps mis en MilliSecondes
1                 0.0
10               0.0
100              0.0
1000            0.0
10000           0.0
100000          0.0
1000000        47.0
10000000      156.0
100000000     1375.0
1000000000   13953.0
1410065408   20172.0

Je trouve ca acceptable comme compléxité

Cordialement

Fred

**jobherzt** · 08/02/2007, 23h36

attention, la complexité ne depend pas seulement de la taille du nombre mais aussi, voire surtout dans certain cas, de la taille des facteurs. tout tes exemples sont des nombres paire, donc deja ca coupe pas mal, d'autant que le dernier est meme divisible 10 fois par 2 :-) donc meme avec l'algorithme naif ca fait tout au plus une vingtaine d'operation ! mais en effet, je doute que ramirami aie a factoriser des nombres gigantesques ! donc ca restera raisonnable dans tous les cas, meme en poussant au max de la capacite de base du langage.. par curiosité, essaie avec 3207711361.

[edit]
en fait, je me demandais meme pourquoi c'etait aussi long.. le fait est que ton nombre a tout de meme un grand facteur... donc forcement il va mouliner un peu avant de se rendre compte que ce facteur est le dernier ! c'est pour ca qu'a chaque fois que tu trouves un nombre, il faudrait que tu divise par ce facteur et que tu recommence a 0 avec le quotient, ca t'eviterai d'aller chercher trop loin des facteurs qui n'existent pas, et accessoirement de reperer les facteur multiples !! j'ai l'impression par exemple que tu n'attrappes le 2 qu'une seule fois, et pas 10 comme il faudrait.

Problème mathématique avec les nombres

Langage Java

Discussions similaires

Partager

Partager