Bonsoir, m'ennuyant je me suis mis en tête de faire un programme qui calcule tous les diviseurs entiers d'un nombre en python (Je précise que j'apprends python depuis hier et que j'en suis à la fin du chapitre sur les boucles) j'ai donc fait un programme qui calcule le modulo d'un nombre (qui vient de l'utilisateur) et qui, quand c'est égal a 0 lui fait savoir en l'affichant, puis le programme rajoute un au modulo et, refait le calcul et cela en continu, jusqu'à ce que le modulo ai atteint le nombre puis il s'arrête. C'est bien, c'est cool ça marche mais, le problème est que : quand je rentre un nombre assez élevé (1 000 000 000) ça met un certain temps... donc, j'ai rajouté du code pour que ça soit un peu plus "rapide" mais je doute qu'il soit optimisé un maximum est-ce que vous auriez des idées ?

Dis-toi que plus il y a de conditions, plus le script sera lent, moins il y a de tests à faire, plus il sera rapide
As-tu une autre version ?

il suffit de tester jusqu'à la racine carrée de x, pas plus

Citation : Lord Casque Noir

il suffit de tester jusqu'à la racine carrée de x, pas plus

Salut, ceci est valable pour un test de primalité, l'auteur veut trouver tous les diviseurs entiers de son nombre

Je te conseille de jeter un oeil du côté des itérateurs avec le mot clé yield.
Autrement, toujours avec les itérateurs :

def diviseurs(nombre):
    return (x for x in range(1,nombre+1) if nombre%x==0)
liste_diviseurs = tuple(diviseurs(<ton nombre>))

On pourrait essayer d'améliorer l'algo en comptant le nombre de diviseurs connus, si arrivé à la racine tu n'as que 1 c'est que le nombre est premier et donc tu affiches le nombre.

Citation : EOF

Salut, ceci est valable pour un test de primalité, l'auteur veut trouver tous les diviseurs entiers de son nombre

Justement, la première chose à faire est de décomposer en facteurs premiers...

Entre tester uniquement jusqu'à la racine carrée et tester jusqu'au nombre il y a la solution de tester uniquement jusqu'à la moitié du nombre. En effet passé la au delà de (nombre/2) le seul diviseur du nombre qui retournera un entier est le nombre lui même et on sait que le résultat sera forcément 1.

def diviseurs(nombre):
    return (x for x in range(2,(nombre/2)+1) if nombre%x==0)
liste_diviseurs = tuple(diviseurs(<ton nombre>))

De même le test divisible par un sera vrai dès lors que le test est effectué sur un entier, mais là on ne gagne pas grand chose en vitesse...

Je ne pensais pas que ça viendrai aussi compliqué en terme de connaissance en programmation python je pense que je vais continuer à lire le cours et refaire ce code plus tard. Merci beaucoup pour votre aide ! De plus ce matin avec un peu plus de recul je me suis aperçu que l'amélioration que je vous ai donné ne sert strictement à rien sauf à ralentir l’exécution je me contenterai donc de mon premier code qui test un par un chaque nombre.

Tu peux quand même remplacer ton:

while o < nombre:

par:

while o < nombre/2:

vu qu'au delà le seul résultat est le nombre lui même. Testes sur un grand nombre pour voir la différence de temps d' exécution.

Autant éviter le while...

def cr(nombre):
	for o in xrange( 1, nombre/2+1 ):
		if not nombre % o:
			print o,

cr( 9999999 )

PS : pypy 5x plus rapide que python sur ce test basique

Et tu peux aussi retirer tous tes "continue" qui ne servent à rien puisque de toute manière il n'y a pas de code après dans la boucle.

Ensuite, je suis d'accord avec Lord Casque Noir, il faut d'abord décomposer en produit de facteur premier et après voir les différentes combinaison de nombre qu'il est possible de faire avec ces facteurs premiers.

Et la par contre, il y a un paquet d'optimisation possible pour calculer le produit des facteurs premier d'un nombre.

Sauf que:

Citation : Petit.oeuf

Je précise que j'apprends python depuis hier et que j'en suis à la fin du chapitre sur les boucles

Donc autant rester sur des choses simples pour l' instant.

Si vraiment il veut utiliser la racine carrée ceci doit suffire et être tout à fait compréhensible :

#!/usr/bin/python
#-*- coding: utf-8 -*-

import math
print("entrez un nombre")
nombre = input()
racine = math.sqrt(nombre)
i = 1
while i <= racine:
	if nombre % i == 0:
		print("{0} est divisible par {1}".format(nombre,i))
	i += 1

Et ça va déjà bien assez vite (presque instantané chez moi et j' ai pas un pc rapide).

Salut

@Lord Casque Noir : Au temps pour moi, j'étais resté dans l'idée de l'algo "on teste tout un par un" pour ne pas trop compliquer le tout mais je suis totalement d'accord sur la combinaison de facteurs premiers.

@Petit.oeuf : Si tu veux tester le code de Lord Casque Noir pense à l'adapter pour ta version de Python :

def cr(nombre):
	for o in range( 1, nombre/2+1 ):
		if not nombre % o:
			print(o),

cr( 9999999 )

import math
print("entrez un nombre")
nombre = input()
racine = math.sqrt(nombre)
i = 1
while i <= racine:
	if nombre % i == 0:
		print("{0} est divisible par {1}".format(nombre,i))
	i += 1

Sauf que dans ce code il oublie le dernier diviseur essaye 42 tu verras 7 n'y sera pas, ça s'arrête à 6.

faudrait comme borne dans le range() : int( math.ceil( math.sqrt(nombre) )) + 1

Euh...

import math
print("entrez un nombre")
nombre = input()
racine = math.sqrt(nombre)
i = 0
while i <= racine:
        i += 1
	if nombre % i == 0:
		print("{0} est divisible par {1}".format(nombre,i))

Bien vu, j' ai édité au dessus le code en modifiant l' endroit du i+=1 et en initiallisant i à 0.
Le pire c' est que c' est la première chose que j' ai vérifié dans ton premier code

Par contre tu pourrais m'expliquer :

import math

et

print("{0} est divisible par {1}".format(nombre,i))

Salut

import math

Importe le module math de la librairie standard, il donne accès à des fonctions mathématiques diverses comme sqrt (racine carrée) et ceil (arrondi à l'entier supérieur).

print("{0} est divisible par {1}".format(nombre,i))

C'est la nouvelle syntaxe de formatage de chaîne de caractère, plutôt que d'utiliser l'ancienne avec %s etc, tu places un marqueur {index_du_paramètre_à_formater} là où il faut remplacer la balise par la valeur d'une variable. Ensuite, tu appelles la fonction format() de l'objet string en lui passant en paramètre les variables à formater dans ta chaîne dans leur ordre d'apparition.

Donc là, le bout de code va remplacer {0} par la valeur de nombre et {1} par la valeur de i.

Bonne soirée.

Tiens, ne faut-il pas un espace après la virgule qui sépare les variables de format() ?
A+

La PEP-8 le préconise fortement, mais bon, c'est pas non plus la mort s'il n'est pas là...