Projet Euler 3 - Pourquoi cette méthode de travail?
Les facteurs premiers de 13195 sont 5, 7, 13 et 29.
Quel est le plus grand facteur premier de le nombre 600851475143?
J'ai résolu ce problème sur le Projet Euler mon propre chemin, qui a été lente, et puis j'ai trouvé cette solution sur un compte github. Je ne peux pas comprendre pourquoi il fonctionne. Pourquoi un certain nombre de facteurs supprimé, égal à un indice? Toute idée?
def Euler3(n=600851475143):
for i in range(2,100000):
while n % i == 0:
n //= i
if n == 1 or n == i:
return i
La fonction renvoie 6857. Il est facile à exécuter.
il ne fonctionnera pas pour 600851475149.
Yep ressemble à un hack pour résoudre un problème spécifique sur le Projet Euler
il ne fonctionnera pas pour 600851475149.
Yep ressemble à un hack pour résoudre un problème spécifique sur le Projet Euler
OriginalL'auteur ballaw | 2012-09-26
Vous devez vous connecter pour publier un commentaire.
Cette fonction de recherche successives facteurs de son entrée. Le premier facteur qu'il trouve sera nécessairement le premier. Après un premier facteur est trouvé, il est divisé à partir de l'original nombre et le processus continue. Par le temps que nous avons divisé tous dehors (en laissant 1, ou si le facteur (i)) nous avons la dernière (la plus grande).
Nous allons ajouter un peu de traçage code ici:
La sortie de ce est:
C'est vrai que pour une solution générale, le haut de gamme doit avoir été la racine carrée de n, mais pour python, appelant
math.sqrt
retourne un nombre à virgule flottante, donc je pense que le programmeur original était de prendre un raccourci paresseux. La solution ne fonctionnera pas en général, mais il a été assez bon pour le projet Euler.Mais le reste de l'algorithme est son.
OriginalL'auteur Ray Toal
Examiner comment il résout pour n=20:
Il est juste de retirer facteurs, et depuis qu'il a déjà supprime les multiples de facteurs premiers (en boucle), de nombreuses valeurs de i sont vraiment juste un gaspillage d'efforts. Les seules valeurs de i qui ont toute chance de faire quelque chose à l'intérieur de la boucle sont des valeurs prioritaires de je. N==i test ne couvre pas le cas de numéros de 25 qui sont des carrés d'un nombre premier.
La gamme semble limitée. Il ne serait pas donner la bonne réponse pour les 2 * (le prochain plus grand nombre premier après 100 000.
OriginalL'auteur hatchet
Personne n'a vraiment répondu à votre question. Le
for
boucle teste chaque numéroi
à son tour. Le test de lawhile
boucle est réussie lorsquei
est un facteur den
; dans ce cas, il réduitn
, puis vérifie si c'est fini en comparanti
à1
oun
. Le test est unwhile
(et pas seulementif
) en casi
divisen
plus d'une fois.Si intelligent, ce n'est pas la façon la factorisation d'entiers par la division de première instance est normalement écrite; elle aussi de ne pas travailler si
n
a un facteur supérieur à 100 000. J'ai un explication sur mon blog. Voici ma version de la fonction, qui répertorie tous les facteurs den
au lieu de simplement le plus grand:Cette fonction gère
2
séparément, puis essaie seulement bizarre facteurs. Il également ne pas placer une limite sur le facteur, au lieu de s'arrêter lorsque le facteur est supérieur à la racine carrée de la durée restanten
, parce que à ce momentn
doit être le premier. Les facteurs sont insérés dans l'ordre croissant, de sorte que le dernier facteur dans la liste de sortie sera le plus grand, qui est celui que vous voulez.mal, et votre downvote (je suppose que c'était) a été déplacée. Je vais vous expliquer. "a juste besoin de la bonne limite supérieure" est erronée parce que le nombre lui-même des modifications lors de ses facteurs sont divisés. Si la limite supérieure est à changer. Mais avec
range
la limite supérieure est avantspécifié. Le a accepté de répondre c'est également à tort à cet égard. J'ai édité la réponse pour améliorer la mise en forme, de sorte que le downvoter a une chance de défaire leurs downvote.OriginalL'auteur user448810