Существует два типа проблем в размещенном коде: управление памятью и алгоритмы.
Получение ресурсов
Программа демонстрирует три вида распределения памяти:
Массив переменной длины . В main, out объявляется как int out[maxi], maxi как переменная, а не постоянная времени компиляции. Это функция C99, она никогда не была частью какого-либо стандарта C ++, даже если она предлагается в качестве функции некоторым компилятором.
bool *arr = new bool[MAX_LIMIT];. Современные рекомендации предлагают избегать использования «голого» * 1022 * для выделения памяти и предпочитать умные указатели, стандартные контейнеры и в целом следовать идиоме RAII , но это даже не главная проблема. MAX_LIMIT слишком велик, чтобы не привести к исключению std::bad_alloc, а также delete никогда не вызывается.
В той же функции есть также al oop, который в конечном итоге получит доступ (маловероятно) выделенная память за пределами: for (unsigned long long int x = 2; x <= MAX_LIMIT; x++) { if (arr[x]) {, x в конечном итоге станет MAX_LIMIT, но до этого у вас не хватит памяти.
std::vector. Это было бы так, если бы только программа не пыталась заполнить вектор primes всеми простыми числами до MAX_LIMIT, что составляет 10 13 -1 или почти 80 ТБ при условии 64- битовый тип.
Алгоритм
Идея состоит в том, чтобы сначала вычислить все возможные простые числа, а затем, для каждого введенного числа, проверить, если таковые имеются из них является фактором. Проблема в том, что максимально возможное число действительно большое, но хорошая новость заключается в том, что вам не нужно вычислять и хранить все простые числа до этого числа, а только до квадрат root этого.
Представьте, что вы попробовали все простые числа до этого квадрата root (назовем это S) и, следовательно, поделили исходное число на любой найденный коэффициент. Если остаток еще есть, это значение не делится ни на одно из упомянутых простых чисел и меньше или равно исходному числу. Это должно быть простое число. Все возможные факторы <= S уже были исключены, и поэтому любой гипотетический фактор> S (что будет результатом деления им? Другого уже проверенного простого числа меньше, чем S).
С точки зрения дизайна, я бы также рассмотрел, как простые числа рассчитываются и хранятся в коде OP. Функция факторизации в основном записывается следующим образом:
unsigned long long int MAX_LIMIT = 9999999999999;
std::vector<unsigned long long int> intFactorisation (unsigned long long int num)
{
static std::vector<unsigned long long int> primes;
// ^^^^^^ ^
if (primes.empty())
{
// generate prime numbers up to MAX_LIMIT using sieve method
}
// Use the primes...
}
Вектор stati c мог быть инициализирован с использованием функции separete и также объявлен const, но с учетом тесной связи с функцией факторизации может быть лучше обернуть эти данные и функциональные возможности в класс, отвечающий за правильное распределение и инициализацию ресурсов.
С введением лямбда-выражений в язык мы можем избежать большей части шаблонов, связанных с обычным функтором класс, так что функция факторизации может быть построена как лямбда с состоянием, возвращаемая следующим образом:
auto make_factorizer(uint64_t max_value)
{
uint64_t sqrt_of_max = std::ceil(std::sqrt(max_value));
// Assuming to have a function returning a vector of primes.
// The returned lambda will accept the number to be factorized and
// a reference to a vector where the factors will be stored
return [primes = all_primes_up_to(sqrt_of_max)](uint64_t number,
std::vector<uint64_t>& factors)
{
uint64_t n{number};
factors.clear();
// Test against all the known primes, in ascending order
for (auto prime : primes)
{
// You can stop earlier, if prime >= sqrt(n)
if (n / prime <= prime)
break;
// Keep "consuming" the number with the same prime,
// a factor can have a multiplicity greater than one.
while (n % prime == 0)
{
n /= prime;
factors.push_back(prime);
}
}
// If n == 1, it has already found and stored all the factors.
// If it has run out of primes or breaked out from the loop,
// either what remains is a prime or number was <= 1.
if (n != 1 || n == number)
{
factors.push_back(n);
}
};
}
Здесь тестируется живая реализация.