Carmichael du théorème prouve que tous les nombres de Fibonacci après 144 a au moins un diviseur premier qui ne divise pas plus tôt le nombre de Fibonacci.
Il n'y a pas beaucoup de nombres de Fibonacci de moins de 10^18; moins de 90.
Faire un tableau de tous les nombres de Fibonacci <= 10^18.
Compte tenu de l'entrée n qui est le produit des nombres de Fibonacci, sa factorisation en nombres de Fibonacci doit inclure tous les nombres de Fibonacci au dessus de 144 qui le divise, répété autant de fois qu'il le divise.
Aller à travers vos nombres de Fibonacci dans l'ordre décroissant, et continuer à diviser n par n'importe quel numéro, qui le divise, jusqu'à ce que vous obtenez à 144.
Maintenant, nous devons être prudents parce que les deux nombres de Fibonacci n'ont pas de facteurs premiers pas vu dans les nombres de Fibonacci. Ce sont 8 et 144. Depuis le 8 est 2^3 et 2 est un nombre de Fibonacci, vous ne pouvez pas vous rendre à votre numéro de unfactorable en nombres de Fibonacci en prenant le 8. En vertu de l'optimisation de votre, vous pourrez toujours choisir de le 8.
Ensuite 144 est le seul facteur que vous pourriez avoir besoin pour rejeter pour un plus petit facteur. Cela peut arriver si 34 ou 21 sont des facteurs, et les 144 élimine le besoin de 2 ou 3.
34 = 2 * 17, 21 = 3 * 7
Qui a été de longue haleine, mais il nous amène à une approche simple.
Aller à travers les nombres de Fibonacci <= n dans l'ordre décroissant jusqu'à ce que vous obtenez à 144, puis passez à 34, puis 21, puis retour à 144 et descendant à 2.
Cela vous donnera l'optimal factorisation sous votre bizarre système de cotation.
----- cet ordre -----
[679891637638612258, 420196140727489673, 259695496911122585, 160500643816367088, 99194853094755497, 61305790721611591, 37889062373143906, 23416728348467685, 14472334024676221, 8944394323791464, 5527939700884757, 3416454622906707, 2111485077978050, 1304969544928657, 806515533049393, 498454011879264, 308061521170129, 190392490709135, 117669030460994, 72723460248141, 44945570212853, 27777890035288, 17167680177565, 10610209857723, 6557470319842, 4052739537881, 2504730781961, 1548008755920, 956722026041, 591286729879, 365435296162, 225851433717, 139583862445, 86267571272, 53316291173, 32951280099, 20365011074, 12586269025, 7778742049, 4807526976, 2971215073, 1836311903, 1134903170, 701408733, 433494437, 267914296, 165580141, 102334155, 63245986, 39088169, 24157817, 14930352, 9227465, 5702887, 3524578, 2178309, 1346269, 832040, 514229, 317811, 196418, 121393, 75025, 46368, 28657, 17711, 10946, 6765, 4181, 2584, 1597, 987, 610, 377, 233, 34, 21, 144, 89, 55, 13, 8, 5, 3, 2]
