c++ - 所有不同质数的和等于 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 开始的。

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