这个过程的逻辑是什么 [英] What is the logic of this process

问题描述

我正在处理 Project Euler 中的问题；我在SO中找到了一个问题.问题和公认的答案说；

I was working on a problem in Project Euler; and I found a question in SO. The question and accepted answer says;

n = 600851475143 
i = 2

while i * i < n:
    while n%i == 0:
        n = n / i
    i = i + 1

print (n)

太棒了.我仍然不明白这个过程有多快，可以在0.00001秒内找到6000亿的最大素因.为此，我尝试了大量的方法和代码，整个过程耗时超过1个小时.

It's just awesome. I still can't understand how this process is so fast and can find the largest prime factor of 600billion in 0.00001 seconds. I tried tons of methods and codes for that, processes took over than 1 hour..

有人能解释一下这些代码的逻辑吗，为什么它是如此之快? while循环在Python中有特殊的位置吗?

Could anyone explain me the logic of this codes and why it's super-fast? is while loop have a special place in Python?

推荐答案

算术基础定理表示每个大于1的整数都可以表示为质数的乘积.例如，数字2100可以这样表示:

The fundamental theorem of arithmetic states that every integer greater than 1 can be represented as the product of prime numbers. E.g., the number 2100 can be represented like so:

2 x 2 x 3 x 5 x 5 x 7

2 x 2 x 3 x 5 x 5 x 7

在这种情况下，我已经安排好了，因此最大的素因数在右边，是7.此算法的作用是从2开始除以n(即去除"该因数)，直到没有更多的素数为止.删除(取模数为0的步骤会在除法之前先将其整除).

I've arranged it so the largest prime factor is on the right, in this case 7. What this algorithm is doing is starting from 2 and dividing n (i.e. "removing" that factor) until there are no more to remove (the modulo 0 step checks that it is divisible cleanly before dividing.)

因此，按照代码，我们将i = 2和n = 2100，或者

So, following the code, we would have i = 2 and n = 2100, or

2 x 2 x 3 x 5 x 5 x 7

2 x 2 x 3 x 5 x 5 x 7

2100可被2(2100 % 2 == 0)整除，也是因为我们在上面的分解中看到2.因此，将其除以2，得出1050，或者

2100 is divisible by 2 (2100 % 2 == 0) and also because we see a 2 in the factorization above. So divide it by 2 and we get 1050, or

2 x 3 x 5 x 5 x 7

2 x 3 x 5 x 5 x 7

再继续除以2，您将得到一个不再可被2整除的数字，即525，或者

Continue dividing by 2, once more, and you get a number that is no longer divisible by 2, that is 525, or

3 x 5 x 5 x 7

3 x 5 x 5 x 7

然后将i增大到3并继续.看看到最后我们将如何获得最高的素数因子?

Then we increase i to 3 and continue. See how by the end we will be left with the highest prime factor?

第一个while循环的i * i < n(实际上应该是i * i <= n)的原因是

The reason for the first while loop's i * i < n (which really should be i * i <= n) is because

如果一个数的除数或因数(不是理想平方)大于其平方根，则另一个因数将小于其平方根.因此，不需要考虑素数大于 n 的平方根的所有倍数.

if one divisor or factor of a number (other than a perfect square) is greater than its square root, then the other factor will be less than its square root. Hence all multiples of primes greater than the square root of n need not be considered.

来自: http://britton.disted.camosun.bc.ca/jberatosthenes. htm

因此，如果i大于n的平方根，则意味着所有剩余因子在n的平方根之下均具有一个已经找到的对". i * i <= n所使用的检查是等效的，但比平方根计算要快.

So if i is greater than the square root of n, that means all remaining factors would have had a "pair" that we already found, below the square root of n. The check used, i * i <= n is equivalent but faster than doing a square root calculation.

之所以如此之快，而其他蛮力方法之所以如此之慢，是因为这将每一步的数目都进行了划分，从而成倍地减少了需要完成的步骤.

The reason this is so quick and other brute force methods are so slow is because this is dividing the number down in each step, which exponentially cuts the number of steps that need to be done.

要看到这一点，600851475143的素因数是

To see this, the prime factorization of 600851475143 is

71 x 839 x 1471 x 6857

71 x 839 x 1471 x 6857

，如果您将代码修改为:

and if you modify the code to read:

n = 600851475143
i = 2

while i * i <= n:
    while n%i == 0:
        print "Dividing by %d" % i
        n = n / i
    i = i + 1

if n > 1:
    print n

您会看到:

>>> 
Dividing by 71
Dividing by 839
Dividing by 1471
6857

这向您显示了它的工作原理.

which shows you that this is exactly how it's working.

这篇关于这个过程的逻辑是什么的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！