分解数量为素数

Question

我试图为素数的分解创建一个Pascal程序，即

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

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

谢谢

Answer 1

质数是一个正好具有两个除数的整数。例如，13是首要的，因为它是整除只有1和13（二除数）。 14不是素数，因为它是由1，2，7和14（4个除数）整除。 4不是素数，因为它是由1，2和4（三级除数）整除。按照惯例，1不是质数，但这里并不重要。

大于1的每个整数都有一个唯一的分解（分解）为素数。换句话说，只有一个（多）素数集合，使他们的产品等于给定的数字。例如：

14 = 2 * 7 
16 = 2 * 2 * 2 * 2 
4 = 2 * 2 
13 = 13 

你的任务是写一个算法，需要对输入的大于1的整数，并输出素数的列表，使得它们的乘积等于输入的号码。

可以说为分解最简单的算法是trial division。

Answer 2

这样做的一个简单的方式是：

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)等

如果你开始与小数字和工作了，你只拔出的主要因素。

所以，对于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。

Answer 3

有两种情况考虑与你输入的号码：

1）的数量是一个素数（在这种情况下，没有分解可能你应该只返回数作为输出）

。

2）的数量不是素数（它可以被分解成质数的产品）

我将概述下面的步骤。请注意，我正在使用另一个着名的算法。我不知道是否有更有效的方法来做到这一点。

1）使用Eratosthenes筛选算法（http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes）查找所有小于您的输入的素数。在这个过程中，您还可以确定您的输入是否为素数。

2）现在，如果您的号码不是素数，请查看将其分开的第一个素数，并继续跟踪您获得的每个数字作为商。

这里是一个很好的例子：http://www.youtube.com/watch?v=9m2cdWorIq8

实施例：

假设你收到输入作为12.

(Operation , Input , Output) 

     -  12  - 
    12/2  6  2 
    6/2  3  2*2 
    3/2  3  2*2 
    3/3  1  2*2*3 

如果打在输入字段中的黄金或1所述的算法停止。

正如你所看到的，关键在于了解素数（2,3,5 ...），这样你就可以将输入与他们分开。你也需要确定你的输入是否是素数。两者都可以用Eratosthenes筛子完成。

Answer 4

基于唐纳德矿工的答案，我做了一个bash函数：

function decompose(){ 
    r=$(
      k=2; 
      N=$1; 
      while [ $N -gt 1 ] && [ $((k ** 2)) -le $N ]; 
      do [ "$((N % k))" == 0 ] && 
      { 
        echo $k; N=$((N/k)); 
      } || let k++; 
      done 
      [ $((k ** 2)) -gt $N ] && echo $N 
    ); 
    echo "$r" | uniq | 
    while read n; 
    do echo "$n^$(
      echo "$r" | grep '^'"$n"'$' | wc -l 
    )"; 
    done | 
    tr '\n' '*' | 
    sed 's/\(\^1\)\?\*$//g; s/\^1\([^0-9]\)/\1/g'; 
    echo; 
} 

一些样本：

$ decompose 768 
2^8*3 
$ decompose 110 
2*5*11 
$ decompose 686567 
7*98081 
$ echo "7*98081" | bc 
686567 

至于说，它可以更快，如果得到的素数，而不是增量k的但对我来说似乎很好。