Discussion :

[ramoucho75020]

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

[droggo]

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.

[bobmidou]

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

[darrylsite]

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

[ramoucho75020]

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

[alex_pi]

Il y a une méthode beaucoup plus efficace en adaptant le crible d'Ératosthène. Je te laisse y réfléchir :-)

[Zavonen]

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.

[Zavonen]

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()

[alex_pi]

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.

[Jedai]

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ï

[Zavonen]

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.

[Jedai]

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ï

[Jedai]

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ï

[alex_pi]

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.

[Jedai]

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ï

[alex_pi]

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;;

[HanLee]

Utilise plutôt Printf.printf, il me semble que c'était largement plus rapide ?

[alex_pi]

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.

[Jedai]

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ï

[alex_pi]

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 :-)