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.

@++

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:

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:

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

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

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]

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 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é....

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 ;)) ~Wonderful Bangladesh~

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_cor­ps_de_nombres_%28GNFS%29

Ca rigole plus là hein?

Bon courage, ~Wonderful Bangladesh~

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.