алгоритм — лучшая программа на С ++ для генерации идеальных чисел
Я сделал следующую программу, которая генерирует совершенные числа, но после того, как она сгенерировала первые 4 числа (до 8128), я долго ждал, но ничего не произошло. Может кто-нибудь, пожалуйста, скажите мне, как сделать программу, которая генерирует совершенные числа, по крайней мере, до переполнения long long int тип данных?
#include<iostream>
using namespace std;
void main() {
unsigned long long int a = 4, sum = 0;
while (true) {
for (int i = 1; i <= (a/2); i++)
{
if (a%i == 0)
{
sum += i;
}
}
if (sum == a) { cout << a<<" "; a += 2; sum = 0; }
else { a += 2; sum = 0; }
}
}
Решение
Чтобы узнать, является ли число идеальным, вам нужно сложить все его делители, а это значит, что сначала вы должны их найти. Вы используете очень медленный подход для этого — в основном, грубая сила всех возможных кандидатов до половины числа. Это займет много времени и сделает его нежизнеспособным вариантом через некоторое время. Если число, которое вы должны проверить, составляет 1 000 000, ваш подход требует 500 000 подразделений. Деления идут медленно. Вы должны изменить подход.
Вам не нужно проверять каждое число, чтобы узнать, является ли оно делителем. Вы можете сделать это: разложить число так, чтобы у вас были его основные множители, а затем сгенерировать все делители.
Факторинг числа может быть невероятно быстрым, чем грубое принуждение всех возможных кандидатов до половины. Даже простой подход может легко пропустить все четные числа (за исключением, конечно, 2), и вы должны остановиться на квадратном корне, а не на половине. Если число составляет около 1’000’000, вам просто нужно ~ 500 делений, то есть нечетных чисел до sqrt (1’000’000). И вы можете легко улучшить его дальше (вы можете найти много материала о том, как оптимизировать поиск основных факторов). Десять лет назад я нашел программу под названием factor.exe, для которой я не могу сейчас обеспечить надежную загрузку (вы можете посмотреть на этот или же этот, но я не проверил, что вы можете там найти, так что загружайте и запускайте на свой страх и риск!), что может составить 60-значное число менее чем за секунду, а через несколько минут это может составить большинство 80-значных номеров. А также Вот это сайт, который с помощью Javascript вычисляет цифры до 20 цифр в среднем за 0,01 секунды (в среднем). Это просто, чтобы дать вам представление о том, насколько быстрым может быть факторинг числа.
После того, как у вас есть простые факторы, которые удобно хранить в векторе, вы можете сгенерировать все делители, комбинируя их. Каждая «комбинация» соответствует выбору, для каждого из них, брать его или нет. Если у вас есть n факторов (кроме 1), у вас есть 2N возможные факторы. Я знаю, экспоненциальный рост не очень хорош, но в основном вы работаете с ограниченным набором, так как n вряд ли будет больше 10 для чисел, которые могут быть сохранены в long long (это просто эмпирически, хотя!). И повторяющиеся факторы могут сделать вещи быстрее (210 на самом деле это не приводит к 1024 различным факторам, на самом деле их всего 10, потому что каждый из них вы найдете много раз), хотя реализация этого требует больше работы.
Таким образом, для числа около 1’000’000 вы можете легко разложить его не более чем на 500 делений, а если у вас есть 10 простых факторов, вы можете иметь 210 = 1024 фактора, каждый из которых требует некоторого умножения (в среднем 5), и в итоге вы должны их сложить. Итак: 500 делений, ~ 5000 умножений и ~ 1000 сумм. Это намного быстрее, чем 500 000 делений, требуемых вашим подходом.
В конце концов этот подход может быть намного быстрее, чем ваш.
Другие решения
Вы можете улучшить скорость факторизации, рассматривая факторы меньше, чем sqrt(a)и получение коэффициента согласования, превышающего это:
template<typename T>
T sum_factors(T n)
{
T sum = 1;
T i = 2;
for (; i * i < n; ++i)
sum += n%i ? 0 : i + n/i;
if (i * i == n)
sum += i;
return sum;
}
Я извлек это как функцию, чтобы можно было тестировать отдельно и улучшать независимо от цикла поиска.
Еще лучше выполнить простую факторизацию и суммировать произведение каждой комбинации (игнорируя комбинацию «все факторы», которая возвращает исходное число, и не забывая комбинацию «не факторы», которая дает 1). Помните, что вы можете прекратить вычислять эту сумму, как только она превысит кандидата (я предлагаю заказать суммирование, чтобы сначала получить самые большие условия, чтобы получить наибольшую выгоду).
Следующий очевидный шаг — разделить работу на несколько ядер:
#include <limits>
#include <iostream>
int main() {
unsigned long long int a;
const auto m = std::numeric_limits<decltype(a)>::max();
#pragma omp parallel for
for (a = 1; a < m; ++a) {
if (sum_factors(a) == a)
#pragma omp critical
std::cout << a << std::endl;
}
return 0;
}
Так как каждый тест полностью независим, этот тест N раза больше кандидатов в данный момент времени, где N количество доступных процессоров. (Скомпилировать с gcc -fopenmp или эквивалент).
Правда, вы захотите использовать Генератор Евклида – Эйлера четных совершенных чисел и знание того, что не существует нечетных совершенных чисел ниже 1e1500 (далеко за пределами диапазона любого примитивного арифметического типа C ++).