Essayer de trouver le plus grand facteur premier

Question

Cela vient de la 3ème question sur le projet Euler

https://projecteuler.net/problem=3

Problème: Les principaux facteurs de 13195 sont 5, 7, 13 et 29. Quelle est la le plus grand facteur premier du nombre 600851475143? Comme c'est un casse-tête, je préférerais ne pas utiliser les méthodes Ruby en boîte. Alors voilà ...

Logique actuelle:
num est le nombre que nous recherchons pour les facteurs premiers.
candidat est un premier facteur potentiel
sqrt est la racine carrée de num

until candidate >= sqrt 

J'ai emprunté cette idée de clayettes de Ératosthène pour trouver des nombres premiers, où l'algorithme vérifie pour divisibilité de chaque numéro jusqu'à la place racine de num. candidat est le nombre à tester si num a un diviseur.

if num % candidate == 0 
... 
end 

Le but est de vérifier si num est divisible par n'importe quoi (a des facteurs). Si num n'est pas divisible par le candidat, le candidat sera incrémenté de 1 jusqu'à ce que l'instruction until soit vraie ou jusqu'à ce que num soit divisible par le candidat.

Si num est divisible par le candidat, alors nous savons que le candidat est premier et il est inséré dans le premier_facteur. Puis récursivité arrive à tester le num nouvellement défini.

prime_factors << num 

Si la boucle until est vrai, alors ce num n'a pas de diviseur et est donc primordiale. Par conséquent, il est inséré dans les facteurs premiers.

Problème:

Le problème est pas qu'il est hors mais minutage qu'il est de donner la mauvaise réponse. Il semble que mon code boucle plus que nécessaire. J'ai ajouté de la journalisation. Je ne sais pas pourquoi, mais je pense que cela a quelque chose à voir avec la pièce de récursion. Certes, je n'utilise jamais la récursivité dans mon code et je voulais l'utiliser pour élargir mes compétences. Donc la récursivité en général est floue pour moi conceptuellement parlant. Toute lecture serait utile aussi.

Que faut-il:
prime_factors = [2,2,19]
prime_factors.last = 19

Qu'est-ce qui se passe réelle:
prime_factors = [2,2,19,19,38]
prime_factors.last = 38

Le code complet:

def largest_prime_factor(num,prime_factors) 
puts "beg fx: num: #{num}, prime_factors: #{prime_factors} 
candidate = 2 
sqrt = Math.sqrt(num) 
loop_count = 0 
until candidate >= sqrt 
    if num % candidate == 0 
    num = num/candidate 
    prime_factors << candidate 
    largest_prime_factor(num,prime_factors) 
    end 
    candidate += 1 
    loop_count +=1 
end 
    puts "outside loop: candidate >= sqrt is #{candidate >= sqrt} num: #{num}, prime_factors: #{prime_factors}, candidate: #{candidate}, sqrt: #{sqrt}, loop: #{loop_count}" 
    gets 
prime_factors << num 
prime_factors.last 
end 

Answer 1

il semble donc l Comme vous l'avez suggéré, le problème est la logique de la récurrence. Le simple fait que vous appeliez une fonction de manière récursive ne signifie pas que le «parent» cesse de fonctionner. Il se contente de rester assis et attend que «l'enfant» finisse, puis continue. C'est là que se passe ce "over looping".Le code n'est en fait pas en boucle mais plutôt en train de finir.

Vous pouvez le voir dans votre instruction puts. Remarquez que, après l'arrêt de la boucle, sqrt augmente parce que le script exécute maintenant le code parent, et non l'après la fin de la partie récursive (child).

Pour le correctif, j'ai fait 2 choses: 1. Créez un booléen qui indique que le bloc de code a subi une récursivité. Si c'est le cas, exécutez ce code, sinon ... exécutez autre chose. 2. Si le candidat n'est pas 2, alors augmentez de 2. Ceci évite de tester tous les nombres pairs à l'exception de 2. Il n'est pas nécessaire de tester d'autres nombres pairs car ce n'est pas un nombre premier.

def largest_prime_factor(num,prime_factors,recursive) 
    candidate = 2 
    until candidate >= Math.sqrt(num) 
    recursive = false 
    if num % candidate == 0 
     num = num/candidate 
     recursive = true 
     prime_factors << candidate 
     largest_prime_factor(num,prime_factors,recursive) 
    end 
    break if recursive 
    candidate == 2 ? candidate += 1 : candidate += 2 
    end 
    prime_factors << num unless recursive 
    prime_factors.last 
end