1

これは、離散数学の割り当てとして取得します。私はこのようにしようとします。

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

4 に答える 4

3

あなたが探しているのは「素数因数分解」と呼ばれます。

http://www.btinternet.com/~se16/js/factor.htmに JavaScript の例があります。

于 2010-08-19T06:39:30.857 に答える
2

与えられた数の素因数を見つけるのは難しい問題です。数値が非常に大きい場合、効率的な因数分解アルゴリズムは不明です。しかし、これは比較的小さい数 N の素因数を見つける単純なアルゴリズムです。

  1. 範囲 2...N のすべての素数をリストします。

  2. リスト内の各素数 p について、N mod p が 0 かどうかを確認します。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 のアルゴリズムまたはQuadratic Sieve アルゴリズムを調べてください。

N までのすべての素数をリストするためのより良い (ただしそれほど単純ではない) 方法は、エラトステネスのふるいです。

アルゴリズムのいくつかのバグ:

  1. おそらく「n mod i = 1」ではなく、「n mod i = 0」と書くつもりだったのでしょう。「n mod i = 0」は、「n は i で割り切れる」または「i は n の約数」と同じです。
  2. アルゴリズムが見つけるのは n のすべての因数ですが、見つける必要があるのは n のすべての素因数です。
于 2010-08-20T15:04:38.913 に答える
1

素数を生成できる場合は、素因数分解を行うことができます。唯一の問題は、それがやむを得ず遅いということです。

簡単な方法は、エラトステネスの伝統的なふるいを使用して素数を生成することです。生成されたプライムごとに（昇順で）、それがあなたの数を分割するかどうかを繰り返しチェックします。それが行われるたびに、それを要因として受け入れ、あなたの数を除算の結果に置き換えます。これ以上分割できない場合は、次の素数に進みます。

したがって、番号が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に減らすと、終了します。

于 2010-08-19T07:07:46.783 に答える
1 
//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
     }
于 2010-08-19T07:06:54.393 に答える