Для решета можно использовать битовый массив. Работать будет медленнее, но не знаю, насколько медленнее.
1. В решете делается упор на большое количество простых операций (сложений),
2. Во втором способе упор на небольшое количество медленных операций (деление с остатком).
По моему опыту, есть 2 практически одинаковых по скорости способа нахождения первых нескольких миллионов простых чисел:
1. решето Эратосфена,
2. проверка делимости нечетных чисел на уже найденные простые числа (величиной до квадратного корня из тестируемого числа).
М-да. Помню, когда пару лет назад в Москву приезжал с лекциями Столлман, он сначала шутил, что стикеры «GNU/Linux inside» стоят по 100 рублей ;)
Но, естественно, раздавал бесплатно.
Запись единицы в i-й бит массива a, состоящего из 32-битных чисел:
Чтение не сложнее. Кстати, можно за раз проверять 32 числа на простоту, сравнивая соответствующую ячейку массива a с 0xffffffff.
1. В решете делается упор на большое количество простых операций (сложений),
2. Во втором способе упор на небольшое количество медленных операций (деление с остатком).
1. решето Эратосфена,
2. проверка делимости нечетных чисел на уже найденные простые числа (величиной до квадратного корня из тестируемого числа).
Но, естественно, раздавал бесплатно.
(Нашел здесь: )
Устанавливать не пробовал, но есть подозрение, что они сделали с FreeBSD примерно то же, что разработчики Calculate Linux сделали с Gentoo.
Download PC-BSD 8.1
Changelog
Release Notes