-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..)

ETC..

#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

下面是一个判断一个数是否为素数的简单函数：

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

这是一些伪代码。首先，我将定义一个函数，它返回除 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

这个对于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 回答