Я пытался получить все простые числа до 600851475143. Для этого я использовал Сито Эратосфена. Это требует от меня создания логического массива такого огромного размера. Плохая идея, вы можете исчерпать память. Любым другим путем. Я попытался использовать строку, используя каждый индекс со значениями 0 и 1 для представления true или false. но метод indexOf тоже возвращает int.
Далее я использую массив 2d для своей проблемы. Любой другой лучший способ хранения такого огромного массива?
Требование к памяти для буфера 600851475143 в лучшем случае составляет 70 ГБ. Это невозможно. Вам нужно либо использовать сжатие, как предложено Stephan, либо найти другой алгоритм для вычисления простых чисел.
У меня была аналогичная проблема, и я использовал бит-набор (в основном, 1 или 0 для желаемого смещения в порядке), и я рекомендую использовать EWAHCompressedBitmap он также сжимает ваш бит, установленный
EDIT
Как сказал Алан, BitSet будет занимать 70 ГБ памяти, но вы можете сделать еще одну вещь: иметь несколько BitSets (последовательные, чтобы вы могли вычислять абсолютную позицию) и загружать в память только BitSet, что вам нужно в тот момент что-то как ленивая нагрузка, в этом случае вы будете контролировать используемую память.
Его не очень удобно запоминать для каждого числа, если оно было простым или нет для такого большого количества (сито очень медленный подход для больших чисел вообще).
Из этой ссылки вы получите представление о том, сколько ожидаемых чисел должно быть меньше X. Для вашего 600-миллиардного диапазона вы можете ожидать примерно 20 миллиардов простых чисел существуют в этом диапазоне. Хранение их надолго [] потребует около 160 ГБ памяти... что значительно больше, чем предлагаемое 70 ГБ для хранения одного бита для каждого номера, половина, если вы исключаете четные числа (2 - единственное четное простое).
Для настольного компьютера 35 ГБ в памяти может быть немного, но хорошая рабочая станция может иметь столько ОЗУ. Я бы попробовал двумерный массив с сдвигом/маскировкой бит.
Я все еще ожидаю, что ваш ситовый код будет запускать значительное количество времени (что-то от нескольких дней до нескольких лет). Я предлагаю вам исследовать более сложные методы первичного обнаружения, чем сито.
Вы можете использовать внутренний API sun.misc.Unsafe HotSpot для выделения большего массива. Я написал blogpost, как имитировать массив с ним Однако это не официальный Java API, поэтому он квалифицируется как хак.
Используйте BitSet. Затем вы можете установить бит любого элемента индекса. 600851475143 2^39, таким образом, принимает только 39 бит внутри (фактически в действительности он будет занимать 64 бита, поскольку он использует длинный).
Вы можете атаковать move upto 2^63, который является массовым для большинства целей