обработка большого количества
Это - проблема 3 от Euler сайта Проекта
Я не отсутствую после решения, но я, вероятно, предполагаю, что Вы будете знать, каков мой подход. К моему вопросу теперь, как я обрабатываю числа, превышающие неподписанный интервал?
Существует ли математический подход для этого, раз так где я могу читать об этом?
7 ответов
Вы пробовали unsigned long long или даже лучше / конкретно uint64_t ?
Если вы хотите работать с числами, превышающими диапазон uint64_t [2 64 -1] [64-битное целое число, без знака], то вам следует изучить bignum: http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic .
600 851 475 143 - это число, указанное в вопросе, а 2 64 -1 равно 18 446 744 073 709 551 615. Он определенно достаточно большой.
Возможно, самый простой способ решить вашу проблему - использовать Python. Версия Python> 2.5 поддерживает встроенные арифметические операции с большой точностью. Точность зависит только от памяти вашего компьютера. Вы можете найти более подробную информацию по этой ссылке .
Используйте
long long
Это поддерживается как в GCC, так и в более новых версиях Visual Studio (я полагаю, 2008 и позже).
В Windows, если ваш компилятор не поддерживает 64-битные целые числа, вы можете использовать LARGE_INTEGER и ULARGE_INTEGER .
Недавно я учил одного знакомого ребенка факторизации простых чисел, алгоритм тривиален при условии, что у вас есть список простых чисел.
- Начиная с 2, разделите его на цель столько раз, сколько сможете, и оставьте нулевой остаток.
- Возьмите следующее простое число (3) и разделите его на цель, как в первом шаге
- Запишите каждый найденный множитель и повторяйте, пока не кончится остаток.
Добавлен, по просьбе, алгоритмический псевдокод:
def factor(n):
"""returns a list of the prime factors of n"""
factors = []
p = primes.generator()
while n > 1:
x = p.next()
while n % x == 0:
n = n / x
factors.append(x)
return factors
Где последовательные вызовы p.next() дают следующее значение в серии простых {2, 3, 5, 7, 11, ...}.
Любое сходство этого псевдокода с реально работающим кодом Python является чисто случайным. Наверное, не стоит упоминать, что определение primes.generator() на одну строку короче (но одна строка - это 50 символов). Изначально я написал этот "код", потому что программа GNU factor не принимала входные данные, где log2(n) >= 40.
long long подойдет для этой задачи. Для других задач проекта Эйлера, которые превышают long long, я бы, вероятно, использовал libgmp (в частности, его классы-обёртки C++).