将数分解为素数

我正在尝试创建一个用于分解素数的帕斯卡程序，即

16 = 2*2*2*2
210 = 2*3*5*7

我应该输入一个数字，然后返回素数分解。我不明白数学意义上的解决方案，有人可以向我解释这个算法或伪代码，只要我明白我正在创建的编程并不是真正的问题。

Thanks

一个简单的方法是：

k = 2
N = 210
while N > 1:
    if N % k == 0:   // if k evenly divides into N
        print k      // this is a factor
        N = N / k    // divide N by k so that we have the rest of the number left.
    else:
        k = k + 1

主要前提是FACTOR(N)等于k * FACTOR(N / k)，如果 k 除 N。所以不断地这样做，直到你不再能因式分解N。这样，你就得到了k1 * k2 * k3 * FACTOR(N / k1 / k2 / k3) etc.

如果你从较小的数字开始并逐渐增加，你只会提取出质因数。

因此，对于 210，您将得到：

k = 2
N = 210

k divides N, so print 2, N becomes 105
k no longer divides N, so k becomes 3
k divides N, so print 3, N becomes 35
k no longer divides N, so k becomes 4
k does not divide N, so k becomes 5
k divides N, so print 5, N becomes 7
k no longer divide N, so k becomes 6
k does not divide N, so k becomes 7
k divides N, so print 7, N becomes 1
N is now equal to 1, so stop.

You get 2 3 5 7 

一个基本的改进是您只需迭代素数。因此，您可以跳过上面示例中的 4 和 6。