Trouver la somme des facteurs de
Pourquoi ce code de retour de la somme des facteurs d'un nombre?
Dans plusieurs Projet Euler problèmes, il vous est demandé de calculer la somme des facteurs comme une partie du problème. Sur l'un des forums de là, quelqu'un a posté le code Java suivant que le meilleur moyen de trouver cette somme, puisque vous n'êtes pas obligé de trouver les facteurs individuels, juste le premier (vous n'avez pas besoin de Java, vous pouvez passer à mon résumé ci-dessous):
public int sumOfDivisors(int n)
{
int prod=1;
for(int k=2;k*k<=n;k++){
int p=1;
while(n%k==0){
p=p*k+1;
n/=k;
}
prod*=p;
}
if(n>1)
prod*=1+n;
return prod;
}
Maintenant, j'ai essayé plusieurs fois et je vois que ça fonctionne. La question est, pourquoi?
Dire que vous facteur 100: 1,2,4,5,10,20,25,50,100. La somme est 217. La factorisation en nombres premiers est 2*2*5*5. Cette fonction vous donne [5*(5+1)+1]*[2*(2+1)+1] = [25+5+1]*[4+2+1] = 217
Affacturage 8: 1,2,4,8. La somme est 15. La factorisation en nombres premiers est 2*2*2. Cette fonction vous donne [2*(2*(2+1)+1)+1]=15
L'algorithme se résume à (à l'aide de Fi à dire la i ' eme de l'indice du facteur F ou F sous i):
return product(sum(Fi^k, k from 0 to Ni), i from 1 to m)
où m est le numéro unique de facteurs premiers, Ni est le nombre de fois que chaque facteur unique se produit dans la factorisation en nombres premiers.
Pourquoi cette formule est égale à la somme des facteurs? Ma conjecture est qu'il est égal à la somme de chaque combinaison unique de facteurs premiers (c'est à dire chaque facteur unique) par l'intermédiaire de la distribution de la propriété, mais je ne vois pas comment.
Petrescu: Yep, merci. Je vais le corriger
OriginalL'auteur Jake Stevens-Haas | 2010-12-17
Vous devez vous connecter pour publier un commentaire.
Regardons le cas le plus simple: quand n est une puissance d'un nombre premier.
Les facteurs de
k^msont 1, k, k^2, k^3 ... k^m-1.Maintenant, regardons à l'intérieur de la boucle de l'algorithme:
Après la première itération, nous avons
k + 1.Après la deuxième itération, nous avons
k(k+1) + 1, ouk^2 + k + 1Après la troisième itération, nous avons
k^3 + k^2 + k + 1Et ainsi de suite...
Comment ça marche pour les nombres qui sont des puissances d'un seul premier. Je pourrais m'asseoir et de la généraliser à tous les numéros, mais vous pourriez vouloir donner un aller vous-même d'abord.
EDIT: Maintenant que c'est la réponse, je vais développer un peu plus, en montrant comment fonctionne l'algorithme sur des nombres avec deux facteurs premiers distincts. Il est alors simple de généraliser que pour les numéros avec une quantité arbitraire de facteurs premiers distincts.
Les facteurs de
x^i.y^jsontx^0.y^0,x^0.y^1...x^0.y^j,x^1.y^0...L'intérieur des boucles pour chaque facteur premier de générer
x^i + x^i-1 + ... + x^0(et de même poury). Alors que nous venons de les multiplier entre nous et nous avons notre somme de facteurs.De se! Si un nombre A=k^mp^n, les facteurs 1,k,k^2...k^m, 1,p,p^2...p^n et chaque combinaison d'un élément à partir de ces deux. Chaque facteur comme une entrée dans une matrice, la première ligne serait de 1,k,k^2...k^m et la première colonne 1,p,p^2,..., p^n. Tout élément ij serait k^ip^j. Le complément serait l'entrée n-i,m-j. La première ligne sera de 1,k,k^2...k^m, le second serait p x de la première ligne, la troisième serait p^2 x de la première ligne et la dernière ligne doit être p^n x de la première ligne. Ainsi, la somme de chaque entrée (qui est, à chaque facteur A) est égal à [1+k+k^2+...+k^m]*[1+p+p^2+...+p^n]. Merci encore
Yup, semble, comme vous le comprenez 🙂
OriginalL'auteur Anon.
L'algorithme est essentiellement la recherche à l'ensemble de tous commandé des sous-ensembles de facteurs premiers de n, qui est analogue à l'ensemble des facteurs de n.
OriginalL'auteur perimosocordiae