-1

演習は次のとおりでした。

1 から 1000 までのすべての数のうち、それらの素因数を足し合わせると素数になる (たとえば、12 には 2、2、3 の素因数があり、合計すると 7 になる) プログラムを設計してください。 . そのアルゴリズムのコードを実装します。

を含む C++ の非常に基本的なものを使用することになっていelse/if, while and for loopsます。もちろん、いくつかの関数を宣言しています。

2、3、5 のような小さなケースに関係なく、まだ正しい出力が得られません。出力は次のとおりです。

6 (sum of factors is 5 : OK)
8 (sum of factors is 6 : WRONG)
10 (sum of factors is 7: OK)
12 (sum of factors is 7: OK)
14 (sum of factors is 9: WRONG)
15 (sum of factors is 8: SO WRONG..)

等..

#include <iostream>
#include <math.h>

using namespace std;

bool CheckPrime (int x)
{
    int count=0;
    for(int i=1; i<=x; i++)
    {
        if( x%i==0 )
        {count++;}
    }
    if ( count==2 )
    {return true;}
    else
    {return false;}

}

int MakeSum (int x)
{
    int Sum = 0;
    for (double i=2; i<sqrt(x); i++)
    {
        if (CheckPrime(i))
        {
            for (double j=1; j<1000; j++)
            {
                int k = pow( i, j);
                if ( (x % k) == 0 )
                {
                    Sum = Sum + i;
                }
            }
        }
    }
    return Sum;
}

int main() // Output cac so tim dc.
{
    int SUM = 0;
    for (int i=0; i < 1001; i++)
    {
        SUM = MakeSum(i);
        if (CheckPrime(SUM))
        {
            cout << i << '\n';
            SUM = 0;
        }
    }
}
4

3 に答える 3

0

ここにいくつかの疑似コードがあります。最初に、1 以外の数の最小因数を返す関数を定義します。素数の場合は 0 を返します。

def FindFactor(x)
  for i from 2 to sqrt(x)
    if x%i==0
      return i
  return 0

これで、数値が素数かどうかを非常に簡単に確認できます。これは、メイン メソッドで役立ちます。

def CheckPrime(x)
  return !FindFactor(x)

最後に、合計の計算を行います。再帰的に行うことの利点は、小さな結果をキャッシュすることで速度の利点を簡単に得られることです。

def MakeSum(x)
  factor1 = FindFactor(x)
  if !factor1
    return x
  factor2 = x / factor1
  return factor1 + MakeSum(factor2)

の各呼び出しでMakeSum、数値の最小因数を見つけます。素数の場合は、数値自体を返します。それ以外の場合は、最小の因数と元の数を最小の因数で割った値で再帰します。

実際、最小の因数はすでに素数であることがわかっているので、わざわざ再帰する必要はありませんでした。これにより末尾呼び出しの再帰が行われるため、適切なコンパイラを想定して、スタックの深さを気にする必要はありません。

于 2013-05-22T05:10:19.550 に答える
0

数値が素数かどうかを判断する単純な関数を次に示します。

function isPrime(n)
    d := 2
    while d * d <= n
        if n % d == 0
            return False
        d := d + 1
    return True

そして、これは数の素因数を決定する同様の関数です:

function factors(n)
    f, fs := 2, []
    while f * f <= n
        if n % f == 0
            append f to fs
            n := n / f
        else f := f + 1
    append n to fs
    return fs

C++ に変換し、演習を完了するためのループとロジックを作成することは、あなたに任せます。

于 2013-05-20T19:04:11.987 に答える
0

これはmakesum関数にどうですか？

makesum(int k)
{
int i;
if(checkprime(k))
{
    return k;
}
for(i=2;i<=(k/2);i++)
{
    if(k%i==0 && checkprime(i))
    {
        int y=k/i;
        sum=i+makesum(y);
    }
}
return sum;
}
于 2013-05-20T18:32:27.877 に答える