需要证明质因数分解的一部分

Question

根据 topcoder Link，我们需要计算数字的平方根以列出其所有质因数...现在我可以在下面的代码中证明我们做对了在for循环中..但我无法弄清楚为什么剩余的数字将是质数，即在我们退出循环后 if (n > 1) printf("%d",n);是什么困扰着我..！你能给我一个正式的证明和例子吗....

 void factor(int n) 
 { 
   int i; 
   for(i=2;i<=(int)sqrt(n);i++) 
   { 
     while(n % i == 0) 
     { 
       printf("%d ",i); 
       n /= i; 
     } 
   } 
   if (n > 1) printf("%d",n); 
   printf("\n"); 
 }

Answer 1

粗略地说，n 的每个因子 i 都有一个辅助因子 i' 使得 i*i'=n，即 n/i。不失一般性假设i=min{i,i'}。然后 i<=sqrt(n)<=i' 成立。该实现旨在仅在忽略 i' 的同时找到 i； space 仅搜索 i 就足够了。

因子 i 的每次出现都被 n /= i 语句取消，这意味着 n 被因子 i' 替换。这里必须考虑两种情况。在第一种情况下，这个因子是质数，这意味着在连续的迭代中不会找到任何因子。在第二种情况下，因子是复合的；这意味着它的因子小于 sqrt(i')<sqrt(n).

但是，这个因子必须大于 i，因为 i 的所有出现都已被 while 循环消除。这意味着剩余因子位于 i+1 和 sqrt(n) 之间，它将在连续迭代中找到。

Answer 2

最初，该过程继续搜索小于其平方根的 n 的最小因数。如果没有，则 n 是质数。所以打印出 n 因为它是一个最小的质因数！

如果你找到一个最小的因子，那么它一定是质数。如果不是，则它是复合的并且具有较小的质因数 - 矛盾。

找到最小的质因数后，将 n 除以那个因数以消除它（记住它可能是 n == i*i*i*...i*r，其中 i 是质因数，r 是残数）。这就是 while(n%i==0) 循环中发生的事情。

最后我们 n 保留了那个残基。所以现在我们想要 r 的最小质因数。我们知道最小的质因数是 i。为什么？因为如果 r 的质因数小于 i 那么 i 就不是 n 的最小质因数。

所以我们可以继续搜索i+1到sqrt(r)，通过对r的尝试划分来找到n的下一个最小质因数。如果我们没有找到任何并且 r>1，那么 r 是最后一个质因数。

通过归纳进行。

在每一轮淘汰之后（进入 while(n%i==0) 循环）我们得到一个我们知道没有质因数的数字 <=i.

需要证明质因数分解的一部分

Needs a proof in a part of prime factorisation

math

proof

prime-factoring

number-theory