c++ - 编写一个算法以返回整数的质数，例如，如果您的输入是 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

Finding the prime factors of a given number is a hard problem. When the numbers are very large, no efficient factorization algorithm is known. But here's a simple algorithm to find the prime factors of a relatively small number N:

1. list all the prime numbers in the range 2...N.

2. for each prime number p in the list, check if N mod p is 0. If so, p is a (prime) factor of N.

How to list all the prime numbers in the range 2...N?

We'll start with an empty list and fill it with prime numbers:

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

Note that this is a very simple algorithm and there are many algorithms which are much better. If you need a more clever solution check out Dixon's algorithm or the Quadratic Sieve algorithm.

A better (but less triavial) way to list all the prime numbers up to N is the Sieve of Eratosthenes.

Some bugs in your algorithm:

1. You probably meant to write "n mod i = 0", not "n mod i = 1". "n mod i = 0" is equivalen to "n is divisible by i" or "i is a factor of n".
2. What your algorithm finds is all the factors of n while what you need to find is all the prime factors of n.

Answer 3

//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
     }

Answer 4

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

一种简单的方法是使用传统的埃拉托色尼筛选法来生成素数。对于生成的每个素数（按递增顺序），反复检查它是否除以您的数字。每次这样做时，接受它作为一个因素，并用除法的结果替换你的数字。当你不能再分裂时，继续下一个素数。

因此，如果您的数字是 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 时，您就结束了。