将数字分解为素数

Question

我正在尝试创建一个用于分解素数的pascal程序,即

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

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

谢谢

Answer 1

一种天真的做法是:

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

主要前提是,如果k除以N ,FACTOR(N)则等于 k * FACTOR(N / k).所以继续这样做,直到你不能再考虑因素N.这样,你得到了k1 * k2 * k3 * FACTOR(N / k1 / k2 / k3)等等.

如果你从较小的数字开始并开始工作,你只会拿出素数因子.

所以,对于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.