将数字分解为质数 [英] Decomposition of number into prime numbers

问题描述

我正在尝试创建用于分解质数的pascal程序，即

  16 = 2 * 2 * 2 * 2210 = 2 * 3 * 5 * 7 

我应该输入一个数字，我应该返回质数分解.我不了解数学上的解决方案，只要我了解我在创建编程的内容并不是问题，有人可以向我解释该算法或伪代码.

谢谢

解决方案

一种简单的方法是:

  k = 2N = 210当N>1:如果N％k == 0://如果k均分为Nprint k//这是一个因素N = N/k//用N除以k，这样剩下的数字就剩下了.别的:k = k + 1 

主要前提是，如果k除以N，则 FACTOR(N)等于 k * FACTOR(N/k).直到您不能再考虑 N 为止.这样，您得到 k1 * k2 * k3 * FACTOR(N/k1/k2/k3)等.

如果您从小数目开始工作，然后再努力，那么只会拉出主要因素.

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

  k = 2N = 210k除以N，因此打印2，N变为105k不再除以N，所以k变为3k除以N，所以打印3，N变成35k不再除以N，所以k变为4k不除以N，所以k变成5k除以N，所以打印5，N变成7k不再除以N，所以k变成6k不除以N，所以k变成7k除以N，因此打印7，N变成1N现在等于1，所以停止.您会得到2 3 5 7 

一个基本的改进就是您只需要遍历素数.因此，在上面的示例中，您可能跳过了4和6.

I'm trying to create a pascal program for decomposition of prime numbers, i.e.

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

I should input a number and I should return the prime numbers decomposition. I don't understand the solution in mathematical sense, could someone explain me this algorithm or pseudo code, as long as I understand what I'm creating programming isn't really an issue.

Thanks

解决方案

A naive way of doing this is to:

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

The main premise, is that FACTOR(N) is equal to k * FACTOR(N / k), if k divides N. So keep doing this over and over until you can no longer factor N. This way, you get k1 * k2 * k3 * FACTOR(N / k1 / k2 / k3) etc.

If you start with small numbers and work up, you'll only pull out the prime factors.

So, for 210, you get:

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 

A basic improvement would be that you only have to iterate through the primes. So, you could have skipped over 4 and 6 in the above example.

这篇关于将数字分解为质数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！