Ограничения размера кучи

Question

Я решаю проблемы с эйлером, используя java для удовольствия в течение нескольких месяцев. Много раз размер кучи ограничивает меня, поэтому я задавался вопросом, что делают другие, когда они достигают этого мертвого и фрустрирующего конца.

Хороший пример проблемы «http://projecteuler.net/problem=432», где у меня есть аккуратная функция, которая решает в течение 10^6 в несколько milisec, но я не могу применить ее к запрашиваемому значению (10^11), потому что он требует целочисленный массив размером 10^11.

EDIT: Чтобы прояснить вопрос. Есть ли способ просеивания больших чисел? Как бы вы, если бы, например, вам нужно было найти первый штрих больше 10^10?

Answer 1

Если вашему решению требуется массив из 10 ** 11 целых чисел, вам необходимо купить компьютер с объемом памяти не менее 745 ГБ. Кажется разумным, что размер кучи по умолчанию не такой большой. Или вам нужно переосмыслить его и не использовать такой огромный массив.

Answer 2

Для действительно больших простых чисел вы не можете получить из сита эратосфенов, потому что максимальная длина решетчатого массива ограничена Integer.MAX_VALUE.

Вы можете вычислить их по самому простому способу -

прайма (N) = если каждому простой в [0, SQRT (N)] не является главным фактором N.

И хранить все большие простые числа, которые вы вычислили в файле или нескольких файлах. Сделайте это один раз, затем повторно используйте их. Загрузите эти простые числа из файла в память, когда вы делаете проблему с эйлером, которая требует больших простых чисел.