Олимпиадное программирование и java

#java

Ну допустим программа будет работать с простыми числами до 100 000. Пишем программу,
которая отдаёт строку вида:
int prostie[] = {2,3,5,7,11,13 ...}

Вставляем в основную программу (которую будем задавать как решение). Дописываем код.
Жмёт Run... Code is too long... Гуглим, оказывается там лимит на 64 кб. В нормальных
программах такие данные выводятся в отдельный файл. Но в олимпиадах как правило можно
сдавать только один файл - сам код. Облом. Что делать?    

Ответы

Ответ 1

Можно хранить простые числа через битовую маску. Это очень эффективно и влазит в
лимит памяти.
Приведу код на Scala, потому что там уже есть готовая структура данных BitSet:
// Простые числа до 500 (для 100000 аналогично, только массив побольше будет)
val bitMask = Array(2891462833508853932L,
    -9222764410617429368L,
    -9212077268751349240L,
    577166812715155618L,
    2488238931731062914L,
    -8637762788791285760L,
    613193408596549664L,
    2261147810570754L)

BitSet.fromBitMask(bitMask).foreach(println)

Т.е. нужно заранее "в оффлайне" подготовить битовую маску через метод BitSet.toBitMask.
А BitSet простых чисел можно заполнить любым удобным способом, хоть полным перебором.