編寫一個算法來返回一個整數的素數，例如，如果你的輸入是10，那麼輸出是列表a中的元素2和5

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

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

如果您可以生成素數，則可以進行素數分解。唯一的麻煩是它不可避免地很慢。

一個簡單的方法是使用傳統的seive of eratosthenes生成素數。對於生成的每個素數（按遞增順序），重複檢查它是否將您的數字分開。每次它，接受它作爲一個因素，並用分部的結果替換你的號碼。當你不能再分開時，轉到下一個素數。

因此，如果您的號碼是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

找到給定數字的主要因素是一個難題。當數字非常大時，沒有有效的分解算法是已知的。但是這裏有一個簡單的算法來找到相對較少數量的素數N：

1. 列出範圍2 ... N中的所有素數。

2. 在列表中的每個素數p，檢查是否N模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's algorithm或Quadratic Sieve algorithm。

一個更好的（但不那麼簡單）的方式列出所有素數最多爲N是Sieve of Eratosthenes。

在你的算法一些錯誤：

1. 你大概的意思是寫 「N MOD I = 0」，而不是 「N MOD I = 1」。 「n mod i = 0」等同於「n可被i整除」或「i是n的因子」。
2. 你的算法發現的是n的所有因子，而你需要找到的是n的所有因子。