A voir également:
- Python factorisation
- Citizen code python avis - Accueil - Outils
- Python est introuvable. exúcutez sans argument pour procúder ó l ✓ - Forum Python
- [PyCharm] Pas d'interpréteur python ✓ - Forum Python
- Extraire données fichier texte python ✓ - Forum Python
11 réponses
Oops je viens de voir que j'ai massacré l'indentation du code. Je ne suis pas certain comment le poster. Je vois bien le script "code" pour les messages: je colle mon code entre les balise
? Hm, je sens que c'est une question débile..
Salut,
Je connais pas PYTHON, j'ai donc eu un peu de mal à interpreter ton code. Pour ma part j'ai créé deux programmes, l'un pour calculer les 100 000 premiers nombres premiers. ensuite je factorise en recherchant comme toi en effectuant des divisions à la difference que je ne teste les divisions que sur les nombres premiers et le temps de calcul est donc plus rapide.
voici mon code pour les nbres premiers:
dim prem(100000)
gosub [load]
open "nbre-premiers.txt" for append as #n
while cnt<100000
scan
trouv=0
while trouv=0
nb=nb+1
block=1
for u=1 to cnt
scan
if prem(u)>nb^0.5 then exit for
ecart=(nb/prem(u))-int(nb/prem(u))
if ecart=0 then block=0
next u
if block=1 then trouv=1
wend
cnt=cnt+1
prem(cnt)=nb
print nb
print #n, nb
wend
close #n
input "recherche terminée";r$
end
[load]
open "nbre-premiers.txt" for input as #n
while eof(#n)=0
line input #n, r$
r=val(r$)
if r<>0 then cnt=cnt+1
wend
close #n
print cnt
input r$
cls
open "nbre-premiers.txt" for input as #n
for i=1 to cnt
line input #n, r$
r=val(r$)
prem(i)=r
print r
next
close #n
nb=prem(cnt)
return
et enfin le code pour la factorisation.
dim prem(100000)
gosub [load]
input nbre
if nbre<2 then print "pas de factorisation possible !":goto [end]
pre=2
nbprem=1
while nbre<>1
scan
if pre>nbre then goto [error]
div=nbre/pre
if int(div)=div then gosub [facto]
if nbprem<>0 then
if nbprem<cnt then
pre=prem(nbprem)
nbprem=nbprem+1
else
pre=pre+1
nbprem=0
end if
else
pre=pre+1
end if
wend
print "Factorisation terminée"
goto [end]
[facto]
pui=0
while int(div)=div
pui=pui+1
nbre=nbre/pre
div=nbre/pre
wend
if len(facto$)<>0 then facto$=facto$+"x"
if pui<>1 then
facto$=facto$+str$(pre)+"^"+str$(pui)
else
facto$=facto$+str$(pre)
end if
print
print facto$
return
[end]
input r$
end
[error]
print "Erreur de factorisation"
print nbre
print pre
goto [end]
[load]
open "nbre-premiers.txt" for input as #n
while eof(#n)=0
line input #n, r$
r=val(r$)
if r<>0 then cnt=cnt+1
wend
close #n
print "le programme à trouvé ";cnt;" nombres premiers !"
print "mise en mémoire de ces nombres en cours."
open "nbre-premiers.txt" for input as #n
for i=1 to cnt
line input #n, r$
r=val(r$)
prem(i)=r
next
close #n
return
en esperant que tu arrivera à retranscrire le langage que j'ai utilisé en PYTHON.
pour info c'est du Liberty BASIC.
je suis en train d'essayer de pousser la taille de ma base de donnée de nombres premiers à 1 000 000.
@++
Je connais pas PYTHON, j'ai donc eu un peu de mal à interpreter ton code. Pour ma part j'ai créé deux programmes, l'un pour calculer les 100 000 premiers nombres premiers. ensuite je factorise en recherchant comme toi en effectuant des divisions à la difference que je ne teste les divisions que sur les nombres premiers et le temps de calcul est donc plus rapide.
voici mon code pour les nbres premiers:
dim prem(100000)
gosub [load]
open "nbre-premiers.txt" for append as #n
while cnt<100000
scan
trouv=0
while trouv=0
nb=nb+1
block=1
for u=1 to cnt
scan
if prem(u)>nb^0.5 then exit for
ecart=(nb/prem(u))-int(nb/prem(u))
if ecart=0 then block=0
next u
if block=1 then trouv=1
wend
cnt=cnt+1
prem(cnt)=nb
print nb
print #n, nb
wend
close #n
input "recherche terminée";r$
end
[load]
open "nbre-premiers.txt" for input as #n
while eof(#n)=0
line input #n, r$
r=val(r$)
if r<>0 then cnt=cnt+1
wend
close #n
print cnt
input r$
cls
open "nbre-premiers.txt" for input as #n
for i=1 to cnt
line input #n, r$
r=val(r$)
prem(i)=r
print r
next
close #n
nb=prem(cnt)
return
et enfin le code pour la factorisation.
dim prem(100000)
gosub [load]
input nbre
if nbre<2 then print "pas de factorisation possible !":goto [end]
pre=2
nbprem=1
while nbre<>1
scan
if pre>nbre then goto [error]
div=nbre/pre
if int(div)=div then gosub [facto]
if nbprem<>0 then
if nbprem<cnt then
pre=prem(nbprem)
nbprem=nbprem+1
else
pre=pre+1
nbprem=0
end if
else
pre=pre+1
end if
wend
print "Factorisation terminée"
goto [end]
[facto]
pui=0
while int(div)=div
pui=pui+1
nbre=nbre/pre
div=nbre/pre
wend
if len(facto$)<>0 then facto$=facto$+"x"
if pui<>1 then
facto$=facto$+str$(pre)+"^"+str$(pui)
else
facto$=facto$+str$(pre)
end if
print facto$
return
[end]
input r$
end
[error]
print "Erreur de factorisation"
print nbre
print pre
goto [end]
[load]
open "nbre-premiers.txt" for input as #n
while eof(#n)=0
line input #n, r$
r=val(r$)
if r<>0 then cnt=cnt+1
wend
close #n
print "le programme à trouvé ";cnt;" nombres premiers !"
print "mise en mémoire de ces nombres en cours."
open "nbre-premiers.txt" for input as #n
for i=1 to cnt
line input #n, r$
r=val(r$)
prem(i)=r
next
close #n
return
en esperant que tu arrivera à retranscrire le langage que j'ai utilisé en PYTHON.
pour info c'est du Liberty BASIC.
je suis en train d'essayer de pousser la taille de ma base de donnée de nombres premiers à 1 000 000.
@++
Salut Pascal,
Hehe, moi aussi j'ai du mal à interpréter ton code MAIS je te remercie chaleureusement pour l'idée de précalculer les nombres premiers. C'est pas con ça.. Surtout que j'ai déjà fait un prog pour ça, manque plus qu'à l'intégrer..
Bon j'essaie de copier mon code avec les indentations, ça sera plus clair. Prions pour que ça marche:
Hehe, moi aussi j'ai du mal à interpréter ton code MAIS je te remercie chaleureusement pour l'idée de précalculer les nombres premiers. C'est pas con ça.. Surtout que j'ai déjà fait un prog pour ça, manque plus qu'à l'intégrer..
Bon j'essaie de copier mon code avec les indentations, ça sera plus clair. Prions pour que ça marche:
print "\n\t\t-----------------Faktoriz v.3,14-------------------\n"
menu_item = 0
while menu_item != "quit":
print "*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*"
print "\n$Type 'do' to Faktoriz(TM) a number"
print "$Type 'quit' if you really insist\n"
menu_item = raw_input("What'll it be? ")
if menu_item == "do":
A = input("\nEl number stp (ouais, entier supérieur ou égal à 2, hein, tu veux pas faire planter mon prog non plus?): ")
div = 2
resultat = str(A) + " = "
print "\n"
while div <= A:
if A%div == 0:
print A, div
puiss = 1
resultat += str(div)
while A%div == 0:
A = A/div
if A == 1:
print A, "Done."
resultat += "^" + str(puiss) + "\n" # pour le dernier facteur (surtout si c'est tous les mêmes e.g. 2^8)
elif A%div != 0: # sinon ça imprime une ligne de trop comme A a changé entre temps
resultat += "^" + str(puiss) + " * " # on change de facteur
pass
else:
print A, div
puiss += 1
else:
div = div + 1
print "\n", resultat
print "\nDon't go!.. :( Punk."
J'ai du nouveau sur ce fichu prog.. Bon, comme suggéré je suis retourné voir mon prog de nombres premiers.
Là j'ai découvert qu'il était grave inefficace: pour chaque nombre (dans la limite spécifiée) il le divisait par TOUS les nombres inférieurs!
Ensuite, j'avoue, j'en ait pris un dans un exemple de Van Rossum. L'idée c'était de faire une sorte de liste des nombres premiers au fur et à mesure et de diviser chaque nouveau nombre par cette liste.
Finalement, j'ai peauffiné mon algo: on spécifie une limite supérieure et le prog trouve tous les nombres entiers dans l'intervalle [2, la limite]. Là encore je créé une liste des nombres premiers trouvés et je divise chaque nouveau nombre par cette liste MAIS la division s'arrête DES que le nombre est divisible par un des premiers dans la liste..
Ca done le petit prog que voici, dont ich bin assez fier:
Bon, sûrement qu'il y a mieux à faire mais j'ai arrêté là, les yeux ensanglantés, la vie sociale annéantie.. ;)
Mais après, en réfléchissant, je me suis dis que c'est pas très utile d'avoir une liste pré-calculée parce qu'en fait, tout ce que fait le programme c'est ajouter 1 au diviseur et voir si le nouveau nombre est un facteur du nombre cherché.
Et il ne commence à ralentir vraiment que vers le million.
Ca prend plus longtemps pour calculer un million de nombres premiers que de laisser mon prog comme ça. Donc après je me suis dit: pourquoi pas, quand on change de diviseur, faire en sorte que ça soit le prochain nombre premier (plutôt que juste incrémenter).
Mais la on se paye le problème de devoir en plus calculer si c'est un nombre premier! J'ai essayé, peut-être que je l'ai mal fait mais mon prog prenait 10 fois plus longtemps!
Finalement la seule optimisation à laquelle j'ai pensée c'est:
Ben, virer tous les diviseurs pairs, puisque le premier truc que fait mon prog c'est essayer de diviser le nombre donné par 2.
Ca laisse évidemment tous les doublons 3*k, 5*k, 7*k (k:impair).. Mais bon: voir si le prochain diviseur est pair c'est rapide.
J'ai tenté et ça accélère légèrement l'affaire..
Des suggestions? :)))
(Bon sang, j'écris beaucoup!)
Là j'ai découvert qu'il était grave inefficace: pour chaque nombre (dans la limite spécifiée) il le divisait par TOUS les nombres inférieurs!
Ensuite, j'avoue, j'en ait pris un dans un exemple de Van Rossum. L'idée c'était de faire une sorte de liste des nombres premiers au fur et à mesure et de diviser chaque nouveau nombre par cette liste.
Finalement, j'ai peauffiné mon algo: on spécifie une limite supérieure et le prog trouve tous les nombres entiers dans l'intervalle [2, la limite]. Là encore je créé une liste des nombres premiers trouvés et je divise chaque nouveau nombre par cette liste MAIS la division s'arrête DES que le nombre est divisible par un des premiers dans la liste..
Ca done le petit prog que voici, dont ich bin assez fier:
upper = input("upper? ")
primes = [2]
for elem in range(3, upper+1):
for x in primes:
if elem % x == 0: # break dès qu'un nombre premier dans la liste est un diviseur
break
else:
n = primes[-1] + 1
while n <= elem:
if elem % n != 0:
n += 1
else: # c'est le prochain nombre premier
primes.append(elem)
break
print primes
Bon, sûrement qu'il y a mieux à faire mais j'ai arrêté là, les yeux ensanglantés, la vie sociale annéantie.. ;)
Mais après, en réfléchissant, je me suis dis que c'est pas très utile d'avoir une liste pré-calculée parce qu'en fait, tout ce que fait le programme c'est ajouter 1 au diviseur et voir si le nouveau nombre est un facteur du nombre cherché.
Et il ne commence à ralentir vraiment que vers le million.
Ca prend plus longtemps pour calculer un million de nombres premiers que de laisser mon prog comme ça. Donc après je me suis dit: pourquoi pas, quand on change de diviseur, faire en sorte que ça soit le prochain nombre premier (plutôt que juste incrémenter).
Mais la on se paye le problème de devoir en plus calculer si c'est un nombre premier! J'ai essayé, peut-être que je l'ai mal fait mais mon prog prenait 10 fois plus longtemps!
Finalement la seule optimisation à laquelle j'ai pensée c'est:
Ben, virer tous les diviseurs pairs, puisque le premier truc que fait mon prog c'est essayer de diviser le nombre donné par 2.
Ca laisse évidemment tous les doublons 3*k, 5*k, 7*k (k:impair).. Mais bon: voir si le prochain diviseur est pair c'est rapide.
J'ai tenté et ça accélère légèrement l'affaire..
Des suggestions? :)))
(Bon sang, j'écris beaucoup!)
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
Bob El Ahn
Messages postés
42
Date d'inscription
dimanche 27 février 2005
Statut
Contributeur
Dernière intervention
25 juillet 2007
8
2 mars 2005 à 16:09
2 mars 2005 à 16:09
Rhaâ, si!!
Quelqu'un a trouvé NETTEMENT plus rapide pour trouver des nombres premiers, le chacal..
Trouvé sur python cookbook, c'est de M. Wang
Si je compile le programme, ça irait plus vite?
Bon, faut que je révise mes maths moi..
Quelqu'un a trouvé NETTEMENT plus rapide pour trouver des nombres premiers, le chacal..
Trouvé sur python cookbook, c'est de M. Wang
def primes(n): if n==2: return [2] elif n<2: return [] s=range(3,n+2,2) mroot = n ** 0.5 half=(n+1)/2 i=0 m=3 while m <= mroot: if s[i]: j=(m*m-3)/2 s[j]=0 while j<half: s[j]=0 j+=m i=i+1 m=2*i+3 return [2]+[x for x in s if x]Bon mais ça m'avance pas tellement..
Si je compile le programme, ça irait plus vite?
Bon, faut que je révise mes maths moi..
sebsauvage
Messages postés
32893
Date d'inscription
mercredi 29 août 2001
Statut
Modérateur
Dernière intervention
21 octobre 2019
15 659
2 mars 2005 à 16:48
2 mars 2005 à 16:48
Hello.
Pour les maths, je suis une bille, je ne te serai donc pas d'une grande aide.
Ceci dit, la factorisation des nombres n'est pas une tâche triviale.
C'est même sur la difficulté de cette opération que repose en partie la sécurité informatique actuelle ! (RSA, SSL, HTTPS, SSH...)
Pour py2exe: 2 Mo. C'est normal.
Python est un langage à machine virtuelle.
Il faut donc fournir la machine virtuelle avec le programme (tout comme Java ou .Net).
Ceci dit, j'ai obtenu des résultats un peu meilleurs en utilisant cx_freeze et en compressant tous les exe/dll/pyd avec UPX.
Si je compile le programme, ça irait plus vite?
Il n'y a pas vraiment de notion de compilation en Python:
le source est pseudo-compilé en bytecode (.pyc) puis est exécuté.
(Voir "La machine virtuelle Python" sur cette page:
http://wikipython.flibuste.net/moin.py/CodesDivers )
Quand on arrive plus à optimiser un algo, sur les processeurs x86 et Pentium, on peut avoir un gain de performances en utilisant psyco.
Voir "psyco" sur cette page:
http://wikipython.flibuste.net/moin.py/QuestionsPratiques
Pour les maths, je suis une bille, je ne te serai donc pas d'une grande aide.
Ceci dit, la factorisation des nombres n'est pas une tâche triviale.
C'est même sur la difficulté de cette opération que repose en partie la sécurité informatique actuelle ! (RSA, SSL, HTTPS, SSH...)
Pour py2exe: 2 Mo. C'est normal.
Python est un langage à machine virtuelle.
Il faut donc fournir la machine virtuelle avec le programme (tout comme Java ou .Net).
Ceci dit, j'ai obtenu des résultats un peu meilleurs en utilisant cx_freeze et en compressant tous les exe/dll/pyd avec UPX.
Si je compile le programme, ça irait plus vite?
Il n'y a pas vraiment de notion de compilation en Python:
le source est pseudo-compilé en bytecode (.pyc) puis est exécuté.
(Voir "La machine virtuelle Python" sur cette page:
http://wikipython.flibuste.net/moin.py/CodesDivers )
Quand on arrive plus à optimiser un algo, sur les processeurs x86 et Pentium, on peut avoir un gain de performances en utilisant psyco.
Voir "psyco" sur cette page:
http://wikipython.flibuste.net/moin.py/QuestionsPratiques
Pour info mon prog en Liberty BASIC fait la même chose que celui de Mr Wang, au lieu de rechercher la divisibilité de tous les nombres premiers qui lui sont inferieurs, on s'arrette à la racinne carré....
Bob El Ahn
Messages postés
42
Date d'inscription
dimanche 27 février 2005
Statut
Contributeur
Dernière intervention
25 juillet 2007
8
2 mars 2005 à 22:52
2 mars 2005 à 22:52
Hehe, n'en rajoute pas! ;-)))
Alors pour la factorisation? Ca marche vite?
Alors pour la factorisation? Ca marche vite?
Bob El Ahn
Messages postés
42
Date d'inscription
dimanche 27 février 2005
Statut
Contributeur
Dernière intervention
25 juillet 2007
8
2 mars 2005 à 22:58
2 mars 2005 à 22:58
Merci!
Oui, pour la "compilation" je redoutais un peu cette réponse..
Je vais essayer la compression avec UPX et je vais sans aucun doute tenter psyco (avec un nom pareil il ne demande que ça!), je ne savais pas s'il changerait grand chose..
Bon je vous tiens au courant, quand j'aurais factorisé une clé RSA je le poste ici en premier, promis ;))
Oui, pour la "compilation" je redoutais un peu cette réponse..
Je vais essayer la compression avec UPX et je vais sans aucun doute tenter psyco (avec un nom pareil il ne demande que ça!), je ne savais pas s'il changerait grand chose..
Bon je vous tiens au courant, quand j'aurais factorisé une clé RSA je le poste ici en premier, promis ;))
Bob El Ahn
Messages postés
42
Date d'inscription
dimanche 27 février 2005
Statut
Contributeur
Dernière intervention
25 juillet 2007
8
4 mars 2005 à 18:57
4 mars 2005 à 18:57
Tiens, j'ai trouvé un nouvel algo pour factoriser.
Pascal au secours!! Comment on implémente ce truc?! ;-))
http://fr.wikipedia.org/wiki/Crible_g%C3%A9n%C3%A9ral_de_corps_de_nombres_%28GNFS%29
Ca rigole plus là hein?
Bon courage,
Pascal au secours!! Comment on implémente ce truc?! ;-))
http://fr.wikipedia.org/wiki/Crible_g%C3%A9n%C3%A9ral_de_corps_de_nombres_%28GNFS%29
Ca rigole plus là hein?
Bon courage,
bon, là c'est le tube d'aspirine ......
si tu l'as pour noël, ça te va ?
je regarde ça et je te tiens au courant.
si tu l'as pour noël, ça te va ?
je regarde ça et je te tiens au courant.
Bob El Ahn
Messages postés
42
Date d'inscription
dimanche 27 février 2005
Statut
Contributeur
Dernière intervention
25 juillet 2007
8
15 mars 2005 à 22:39
15 mars 2005 à 22:39
Mon héros!!
Bon courage!!
;))
Bon courage!!
;))
Utilisateur anonyme
21 nov. 2011 à 18:27
21 nov. 2011 à 18:27
quand j'éxecute ton prog , on m'écrit error pr la ligne , je cite : raw_input, l'ordi me dit "it is not defined"
Je ne comprend pas
Merci
Je ne comprend pas
Merci