все суммы различных простых чисел равны 100
У меня есть домашнее задание, чтобы написать код, который находит все суммы различных простых чисел равными 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();
}
Решение
Я забыл название алгоритма, но идея заключается в следующем:
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.
Идея для улучшения: вы можете запустить тело цикла в новом потоке, так как потоки не влияют друг на друга
Другие решения
Вы узнали о проблема подмножества сумм?
Он задает следующий вопрос:
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 онлайн, который вычисляет все подмножества (здесь один вам может понадобиться адаптироваться) и просто накормить его желаемым вкладом.
detector