IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Mathématiques Discussion :

Nombres premiers entre eux


Sujet :

Mathématiques

  1. #1
    Membre régulier
    Homme Profil pro
    Inscrit en
    mars 2008
    Messages
    70
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Secteur : Finance

    Informations forums :
    Inscription : mars 2008
    Messages : 70
    Points : 76
    Points
    76
    Par défaut Nombres premiers entre eux
    Bonjour ,


    j'ai un petit souci algorithmique . En faite j'ai reflechis pendant un moment et je n'arrive pas a definir un algorithme qui a partir d'un nombre quelquonque me genere tous les nombres qui sont premier avec ce premier nombre . premier entre eux signifie que leur pgcd = 1 .

    En faite j'ai reussi a ecrire un petit programme en utilisant l'algorithme d'euclide pour me dire si 2 nombres sont premiers entre eux . Mais moi j'ai en faite le premier nombre mais pas le second et j'aimerais le generer automatiquement et il faut qu'il soit premier avec l'autre ...



    Si quelqu'un a des suggestions ou quelques pistes ne serai ce qu'algorithmique je coderai ca moi meme .


    Merci

  2. #2
    Expert confirmé

    Inscrit en
    août 2006
    Messages
    3 866
    Détails du profil
    Informations forums :
    Inscription : août 2006
    Messages : 3 866
    Points : 5 470
    Points
    5 470
    Par défaut
    Fao,

    Il suffit que le nouveau nombre n'ait aucun facteur premier en commun avec le 1er.

    Il faut donc :

    - un tableau des nombres premiers, jusqu'à une limite que tu choisis

    - décomposer le 1er nombre

    - générer le deuxième nombre en prenant des nombres premiers n'apparaissant pas dans la décomposition du 1er, et en les multipliant.
    "Mon pied droit est jaloux de mon pied gauche.
    Quand l'un avance, l'autre veut le dépasser.
    Et moi, comme un imbécile, je marche !"
    [Raymond Devos]

  3. #3
    Membre habitué Avatar de bobmidou
    Profil pro
    Inscrit en
    avril 2008
    Messages
    121
    Détails du profil
    Informations personnelles :
    Localisation : Canada

    Informations forums :
    Inscription : avril 2008
    Messages : 121
    Points : 149
    Points
    149
    Par défaut
    salut

    Voici une solution parmi d'autres
    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
     
    void premier(int,int);
     
    int main()
    {
    	premier(7,40); // nombres premiers avec 7 et inférieurs à 40
     
    	return 0;
    }
     
    // nombres premiers avec x et inférieurs à max
    void premier(int x, int max)
    {
    	bool nombre_premier = true;
    	for(int j = 2 ; j <= max ; j++)
    	{
    		nombre_premier = true;
    		for(int i = 2 ; i <= j ; i++)
    		{
    			if ((x % i) == 0 && (j % i) == 0 )
    			{
                                    nombre_premier = false;
    				break;
    			}
    		}
    		if(nombre_premier)
    		printf("%d  " ,j);
    	}
    }
    Bonne chance
    --<< Il n y a que les clous qui ne plantent pas >>---

  4. #4
    Rédacteur
    Avatar de darrylsite
    Profil pro
    Inscrit en
    juillet 2007
    Messages
    1 299
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : juillet 2007
    Messages : 1 299
    Points : 2 501
    Points
    2 501
    Par défaut
    Salut Droggo.
    Je crois qu' on doit trouver une solution à partir de ce qu' il à deja fait.
    Si tu as réussi à coder l' algorithme d' euclide, c' est deja super. Ce qu' il te faut faire, c' est de transformer ce programme en fonction qui te renvoie par exemple 1 si les deux sont premier et autre chose sinon.
    Pour trouver le deuxieme nombre, tu peux le generer au hazard en utilisant rand().
    Tu fais une bloucle qui s' arrete quand leur pgcd 1.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
     
    while (pgcd(nombre1,nombre2=rand()*1000) !=1);
    //nombre2 est ce que tu cherche

  5. #5
    Membre régulier
    Homme Profil pro
    Inscrit en
    mars 2008
    Messages
    70
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Secteur : Finance

    Informations forums :
    Inscription : mars 2008
    Messages : 70
    Points : 76
    Points
    76
    Par défaut
    Merci bcp effectivement j 'avais deja codé un prog qui lors a partir d'un nombre defini demande a l'utilisateur d'entrer le second et tout cela dans une boucle while pgcd different de 1 .



    Pour les autres solution je vous remercie bcp je pense avoir compris je vais mettre un coté automatis& dans le programme qui va choisir le second .


    Merci encore

  6. #6
    alex_pi
    Invité(e)
    Par défaut
    Il y a une méthode beaucoup plus efficace en adaptant le crible d'Ératosthène. Je te laisse y réfléchir :-)

  7. #7
    Rédacteur
    Avatar de Zavonen
    Profil pro
    Inscrit en
    novembre 2006
    Messages
    1 772
    Détails du profil
    Informations personnelles :
    Âge : 74
    Localisation : France

    Informations forums :
    Inscription : novembre 2006
    Messages : 1 772
    Points : 1 913
    Points
    1 913
    Par défaut
    Il y a peut être une autre piste à explorer:
    Le théorème de Bezout:
    a,b premiers entre eux ssi on peut trouver u et v entiers tels que au+bv=+/-1
    Il existe plusieurs théorèmes sur les bornes entre lesquelles on peut trouver u et v.
    Disons m(a,b) <= u,v <= M(a,b)
    Donc pour tester si a et b sont premiers entre eux on peut faire 2 boucles imbriquées pour u, v allant de m à M on calcule ua+bv si on trouve 1 ou -1 on sort avec une conclusion positive, si on va au bout des boucles négatif.
    Ce qu'on trouve est plus important que ce qu'on cherche.
    Maths de base pour les nuls (et les autres...)

  8. #8
    Rédacteur
    Avatar de Zavonen
    Profil pro
    Inscrit en
    novembre 2006
    Messages
    1 772
    Détails du profil
    Informations personnelles :
    Âge : 74
    Localisation : France

    Informations forums :
    Inscription : novembre 2006
    Messages : 1 772
    Points : 1 913
    Points
    1 913
    Par défaut
    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
    def pgcd(a,b):
        if a%b==0:
            return b
        else:
            return pgcd(b,a%b)
     
    #teste si a et b sont premiers entre eux
    def PremiersEntreEux(a,b):
        return pgcd(a,b)==1
     
    #Trouve les n nombres suivants a et premiers avec lui
    def Trouveb(a,n):
        b=a+1
        while n>0:
            if PremiersEntreEux(a,b):
                print b,
                n=n-1
            b=b+1
     
    def main():
        Trouveb(130,10)
    if __name__ == '__main__':
        main()
    Ce qu'on trouve est plus important que ce qu'on cherche.
    Maths de base pour les nuls (et les autres...)

  9. #9
    alex_pi
    Invité(e)
    Par défaut
    Ca me parrait vraiment lourd comme méthode. Avec la mienne, coder sur un coin de table, je trouve les nombre premier avec 223092870 compris entre 1 et 4194302 en 1,8s (ocamlopt, sur une machine vieille de 3 ans). Bref, ça va raisonnablement rapidement.

  10. #10
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : avril 2003
    Messages : 6 245
    Points : 8 560
    Points
    8 560
    Par défaut
    Citation Envoyé par alex_pi Voir le message
    Ca me parrait vraiment lourd comme méthode. Avec la mienne, coder sur un coin de table, je trouve les nombre premier avec 223092870 compris entre 1 et 4194302 en 1,8s (ocamlopt, sur une machine vieille de 3 ans). Bref, ça va raisonnablement rapidement.
    Je soupçonne qu'on a la même méthode mais que tu n'utilises pas une structure de donnée très performante dans ton programme. De mon côté, en utilisant un programme Haskell assez naïf, j'obtiens le même résultat (68612 nombres premiers avec 223092870 dans cet intervalle, non ?) en 66 ms :
    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
    import Data.Array.ST
    import Control.Monad
    import Data.Array.Unboxed
     
    createCrible :: Int -> Int -> UArray Int Bool
    createCrible a n = runSTUArray $ do
                         arr <- newArray (1,n) True
                         forM_ (primeFactors a) $ \p -> do
                           forM_ [p,p+p..n] $ \m -> do
                             writeArray arr m False
                         return arr
     
    primeFactors :: Int -> [Int]
    primeFactors n | 2 `divides` n = 2 : pfOver 3 (n `superDiv` 2)
                   | otherwise = pfOver 3 n
     
    divides d m = m `rem` d == 0
     
    pfOver p n 
        | p > n = []
        | p `divides` n = p : pfOver (p+2) (n `superDiv` p)
        | otherwise = pfOver (p+2) n
     
    superDiv n d | d `divides` n = superDiv (n `quot` d) d
                 | otherwise = n
     
    main = print . length . filter id . elems . createCrible 223092870 $ 419430
    Alternativement, en évitant une formulation impérative, on peut écrire ceci : (mais c'est un peu plus lent, 0,1s)
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    createCrible :: Int -> Int -> UArray Int Bool
    createCrible a n = accumArray (flip const) True (1,n) $
                          [(m,False)| p <- primeFactors a, m <- [p,p+p..n]]
    --
    Jedaï

  11. #11
    Rédacteur
    Avatar de Zavonen
    Profil pro
    Inscrit en
    novembre 2006
    Messages
    1 772
    Détails du profil
    Informations personnelles :
    Âge : 74
    Localisation : France

    Informations forums :
    Inscription : novembre 2006
    Messages : 1 772
    Points : 1 913
    Points
    1 913
    Par défaut
    Mais moi j'ai en faite le premier nombre mais pas le second et j'aimerais le generer automatiquement et il faut qu'il soit premier avec l'autre ...
    Je crois que les besoins du PO sont en fait bien modestes. Ayant un nombre il veut un autre nombre premier avec lui. Cela n'a pratiquement rien à voir avec la notion de nombre premier.
    Ce qu'on trouve est plus important que ce qu'on cherche.
    Maths de base pour les nuls (et les autres...)

  12. #12
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : avril 2003
    Messages : 6 245
    Points : 8 560
    Points
    8 560
    Par défaut
    Citation Envoyé par Zavonen Voir le message
    Je crois que les besoins du PO sont en fait bien modestes. Ayant un nombre il veut un autre nombre premier avec lui.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    nombrePremierAvec n = 1
    ?

    Vu les performances de la solution proposée par alex_pi (du moins de ce que je pense qu'il propose... ). Ca me semble une relativement bonne réponse, même si la question n'était pas "trouver tous les nombres premier avec a" comme nous l'avions compris.

    --
    Jedaï

  13. #13
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : avril 2003
    Messages : 6 245
    Points : 8 560
    Points
    8 560
    Par défaut
    La solution de Zavonen s'en sort relativement bien également :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    main = print . length . trouve 223092870 $ 68612
     
    pgcd a b | r == 0 = b
             | otherwise = pgcd b r
        where r = a `rem` b
     
    trouve a n = take n . filter ((==1) . pgcd a) $ [1..]
    prend 300ms à s'exécuter chez moi.

    Néanmoins, l'idée d'Alex_pi reste plus efficace, car :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    trouve a n = take n . filter (\b -> not $ any (`divides` b) pfa) $ [1..]
        where pfa = primeFactors a
    ne prend que 130ms avec le même "main".

    --
    Jedaï

  14. #14
    alex_pi
    Invité(e)
    Par défaut
    Citation Envoyé par Jedai Voir le message
    Je soupçonne qu'on a la même méthode mais que tu n'utilises pas une structure de donnée très performante dans ton programme.
    Si je comprends bien ton code Haskell (ce qui n'est pas gagné puisque je ne m'y suis toujours pas mis :-)) oui, on utilise bien la même méthode. La différence de temps d'exécution peut s'expliquer
    1) ma machine frole le poussif (P IV mono coeur à 3.2 GHz)
    2) une programmation à la va vite la nuit
    3) tu sembles avoir oublier un 2 Mes "benchmarks" sont pour 4194302, pas pour 419430 (c'est simplement la limite de taille des tableau en Caml).

    Après, je n'ai pas testé la méthode par PGCD, mais il me semble que le crible est plus "joli", et de toutes façon nettement plus efficace si le nombre de résultats demandés est beaucoup plus gros que le nombre à comparé. Après, c'est sûr que si on en demande que 4 ou 5, autant faire un PGCD.

  15. #15
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : avril 2003
    Messages : 6 245
    Points : 8 560
    Points
    8 560
    Par défaut
    Effectivement, le 2 change un peu les choses ! Je tombe à 300ms avec mon premier crible, 400ms pour le second, 700ms avec le second "trouve" et ... 2,9s pour le premier trouve, celui utilisant le PGCD.

    (Par ailleurs ton ordinateur n'a aucune excuse, ici j'ai un portable vieux de 3 ans aussi, monocoeur 1.73GHz (Pentium M tout de même) !! )

    --
    Jedaï

  16. #16
    alex_pi
    Invité(e)
    Par défaut
    En fait, quand je supprime l'output des résultats, je suis à 0,18 s, mais quand je le mets, je suis à 1,04 s (même avec envoie vers /dev/null)... print_int serait-il d'une lenteur effroyable ?

    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
     
    let rec div_tot n d = 
      if n mod d = 0 then div_tot (n / d) d else n ;;
     
    let rec fact_imp d n =
      if d > n then [] else
        if n mod d = 0 
        then d :: (fact_imp (d + 2) (div_tot n d))
        else fact_imp (d + 2) n;;
     
    let facteurs n = 
      if n mod 2 = 0 
      then 2 :: (fact_imp 3 (div_tot n 2))
      else fact_imp 3 n ;;
     
     
    type premier_avec = 
        PremierAvec
      | NonPremierAvec
     
    let rec marquer_reg t i s m = 
      if i < Array.length t then
        (t.(i) <- m;
         marquer_reg t (i + s) s m ;)
     
     
    let nbr_prem x n =
      let premier_avec = Array.make (n + 1) PremierAvec in
      let fp = facteurs x in
      List.iter (fun s -> marquer_reg premier_avec s s NonPremierAvec) fp;
      Array.iteri (fun i x -> if x = PremierAvec then (print_int i; print_newline())) premier_avec
     
    let _ = nbr_prem 223092870 4194302;;

  17. #17
    Membre éclairé Avatar de HanLee
    Profil pro
    Inscrit en
    mai 2004
    Messages
    738
    Détails du profil
    Informations personnelles :
    Âge : 34
    Localisation : France, Rhône (Rhône Alpes)

    Informations forums :
    Inscription : mai 2004
    Messages : 738
    Points : 854
    Points
    854
    Par défaut
    Utilise plutôt Printf.printf, il me semble que c'était largement plus rapide ?

  18. #18
    alex_pi
    Invité(e)
    Par défaut
    Citation Envoyé par HanLee Voir le message
    Utilise plutôt Printf.printf, il me semble que c'était largement plus rapide ?
    C'est au contraire beaucoup plus lent ! Là, ça met 4.58s avec Printf. La construction de la chaine est plus complexe.

  19. #19
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : avril 2003
    Messages : 6 245
    Points : 8 560
    Points
    8 560
    Par défaut
    Si je fais ça, pour qu'on calcule la même chose :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    let nbr_prem x n =
      let premier_avec = Array.make (n + 1) PremierAvec in
      let fp = facteurs x in
      let nbPrem = ref 0 in
      List.iter (fun s -> marquer_reg premier_avec s s NonPremierAvec) fp;
      Array.iter (fun x -> if x = PremierAvec then incr nbPrem) premier_avec;
      print_int !nbPrem
    J'obtiens une exécution en 230ms, contre 200ms pour mon plus rapide programme Haskell (j'ai changé de machine), on peut donc dire qu'en fait ça se tient pas mal.
    Par contre je peux cribler plus loin (les tableaux en Haskell ne sont pas aussi limités en taille), par exemple je peux cribler les 10_000_000 premiers nombres en 450ms.
    --
    Jedaï

  20. #20
    alex_pi
    Invité(e)
    Par défaut
    Citation Envoyé par Jedai Voir le message
    Si je fais ça, pour qu'on calcule la même chose :
    Je n'avais pas compris que tu ne calculais que le nombre d'éléments.

    Pour chipoter, je préfère

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
     
    let nbr_prem x n =
      let premier_avec = Array.make (n + 1) PremierAvec in
      let fp = facteurs x in
      List.iter (fun s -> marquer_reg premier_avec s s NonPremierAvec) fp;
      let nbPrem = 
        Array.fold_left (fun count x -> if x = PremierAvec then count + 1 else count) 0 premier_avec in
      print_int nbPrem
    Mais ça revient au même :-)

    Bref, j'espère qu'avec tous les exemples de code, ramoucho a compris de quoi on parlait :-)

Discussions similaires

  1. Réponses: 3
    Dernier message: 30/11/2014, 17h36
  2. Nombres premiers entre eux (coprime)
    Par Jerome Briot dans le forum Téléchargez
    Réponses: 0
    Dernier message: 04/09/2009, 20h07

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo