所有不同质数的和等于 100

Question

我有一个作业要编写一个代码，它发现不同质数的所有总和等于 100。我为 2 元素总和编写了这段代码，但我不知道如何对更多元素进行迭代。它必须用 c++/clr 编写。如果你能帮助我，我会很高兴。

#include "stdafx.h"
using namespace System;
using namespace System::Collections::Generic;

int main(array<System::String ^> ^args)
{
List<int> ^primes = gcnew List<int>();
primes->Add(2);
primes->Add(3);
for (int i = 3; i < 100; i++)
{

    double square = Math::Sqrt(i);
    for (int j = 2; j <= square ; j++)
    {
        if(i%j == 0)break;
        else if (j == Math::Floor(square))primes->Add(i);
    }
}
int primesQuantity = primes->Count;
int s = 0;
for (int i = 0; i < primesQuantity; i++)
{
    for (int k = 0; k < primesQuantity; k++)
    {
        if (i != k)
        {
            s = primes[i] + primes[k];

            if (s == 100)
            {
                Console::WriteLine("{0}+{1}=" + s, primes[i], primes[k]);
            }
        }

    }
}
Console::ReadKey();
}

Answer 1

我忘记了算法的名称，但思路如下：

1) 你需要产生所有可能的元素组合。这是通过使用位掩码实现的。你取一个数，然后取读取位设置为1，例如：5 = 101，所以你只取0和2位。

2) 求和。

代码示例：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    int primes[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
    vector<vector<int> > res;
    // Here is a binary number that contains 25 of 1.
    // I used 25 because this is the number of prime number from 1 to 100
    for (auto i = 0; i < 0b1111111111111111111111111; i++)
    {
        vector<int> group;
        auto val = i;
        auto bits = 0;
        for (auto j = val; val; val >>= 1, ++bits)
            if (val & 0x1 == 1) group.push_back(bits);
        auto sum = std::accumulate(group.begin(), group.end(), 0,
        [&primes](int acc, int x){return acc + primes[x];});
        if (sum == 100) res.push_back(group);
    }

    for (auto el : res) {
        for (auto ele : el)
            cout << ele << " ";
        cout << endl;
    }
    return 0;
}

结果：

0 1 2 3 4 5 6 7 8
0 2 4 5 6 8 9
3 4 5 6 8 9
0 1 4 5 7 8 9
2 4 5 7 8 9
0 1 3 6 7 8 9
2 3 6 7 8 9
....
1 24

这是素数数组中元素的索引。请注意，它们是从 0 开始的。

改进想法：您可以运行新线程中的循环主体，因为线程不会相互影响

Answer 2

您了解 subset sum problem 吗？它会问以下问题：

Given a set of integers A and an integer s, does any non-empty subset sum to s?

在你的例子中，s==100 和 A == {2,3,5,7, ... 97}。

您可以在线找到计算所有子集的 C 代码（这里是 one 您可能需要调整），然后将其输入您想要的输入即可。

所有不同质数的和等于 100

all sums of different prime numbers equals 100

c++

clr

numbers

equals

结果：