编写一个算法来返回整数的素数，例如，如果您的输入是 10，则输出是包含元素 2 和 5 的列表 a

Question

这是我在离散数学中得到的作业。 我尝试这样做。

procedure prime_numbers (x)
  n:= 1
  for i:= to n<=x do
    n mod i=1 then
      return (prime)
end prime_number.

Answer 1

您正在寻找的称为“素数分解”。

在 http://www.btinternet.com/~se16/js/factor.htm 你会发现一个 JavaScript 示例。

Answer 2

找到给定数字的质因数是一个难题。当数字非常大时，不存在有效的因式分解算法。但这里有一个简单的算法来查找相对较小的数字 N 的素数因子：

1. 列出 2...N 范围内的所有素数。

2. 对于列表中的每个素数 p，检查 N mod p 是否为 0。如果是，则 p 是 N 的（素数）因子。

如何列出 2...N 范围内的所有素数？

我们将从一个空列表开始，并用素数填充它：

for n=2...N:
   foreach p in your list:
      if n mod p is 0 then continue
   insert n to the list

请注意，这是一个非常简单的算法，并且有许多算法更好。如果您需要更聪明的解决方案，请查看 Dixon 算法 或 二次筛算法。

列出直到 N 的所有素数的更好（但不那么琐碎）的方法是埃拉托斯特尼筛法。

你的算法中的一些错误：

1. 你可能想写“n mod i = 0”，而不是“n mod i = 1”。 “n mod i = 0”相当于“n 可被 i 整除”或“i 是 n 的因数”。
2. 你的算法找到的是n的所有因子，而你需要找到的是n的所有素数因子。

Answer 3

如果你可以生成素数，你就可以进行素因数分解。唯一的问题是它不可避免地很慢。

一种简单的方法是使用传统的埃拉托斯特尼序列来生成素数。对于生成的每个素数（按递增顺序），重复检查它是否能整除您的数字。每次出现时，接受它作为一个因子，并用除法的结果替换你的数字。当你无法再整除时，继续处理下一个素数。

因此，如果您的数字是 20，您首先会尝试质数 2。

20/2 = 10, so accept factor 2 and use number 10
10/2 = 5, so accept factor 2 and use number 5
5/2  = 2 rem 1, so move onto prime 3
5/3  = 1 rem 2, so move onto prime 5
5/5  = 1, so accept factor 5 and use number 1

当您将剩余数字减少到 1 时，您就结束了。

Answer 4

//Copyright 1998 Henry Bottomley (written 23 December)
//All rights reserved

  function factorise(numm)                      // To calculate the prime factors of a number
     {
      var newnum = numm;                        // Initialise
      var newtext = "";
      var checker = 2;                          // First possible factor to check

      while (checker*checker <= newnum)         // See if it is worth looking further for factors 
         {      
          if (newnum % checker == 0)            // If the possible factor is indeed a factor...
             { 
              newtext = newtext + checker;      // ...then record the factor
              newnum = newnum/checker;          //    and divide by it
              if (newnum != 1)                  //    then check whether it is not last...
                 {
                  newtext = newtext + ".";      //    ...and if so prepare for the next
                 }
             }
          else                                  // otherwise...
             {
              checker++;                        // try the next possible factor
             }
         }
      if (newnum != 1)                          // If there is anything left at the end...
         {                                      // ...this must be the last prime factor
          newtext = newtext + newnum;           //    so it too should be recorded
         }
      if (newtext == "" + numm)                 // If the only prime factor is the original...
         {
          newtext = "Prime: " + newtext;        // ...then note that it must have been prime.
         }

      return newtext;                           // Return the prime factors
     }