Есть что нибудь быстрее решета Эратосфена?

но коечто есть:

#!/usr/bin/perl -sw

use Quantum::Superpositions;

sub is_prime { return $_[0]==2 || $_[0] % all(2..sqrt($_[0])+1) != 0 }

do{print "$_ - простое число\n" if is_prime($_)} for map {2*$_+1} 1..1000;

у меня AthlonXP2100+ (640 Mb RAM) с установленным ASPLinux, ядро 2.4.22, perl 5.8.0 и соответственно такие данные для измерения скорости:

для первого примера на интервале 1000000000 - 1000000050:

[vilfred@mobile100 vilfred]$ time ./yy.pl
1000000007 - простое число
1000000009 - простое число
1000000021 - простое число
1000000033 - простое число

real 0m16.285s
user 0m16.250s
sys 0m0.030s
[vilfred@mobile100 vilfred]$

а для этого примера реализации решета Эратосфена (может и както по иному можно написать - не знаю), машина ругается на большие значения (по моему выедается вся оперативная память):

#!/usr/bin/perl
$N = 1000000050;
@L = (1) x $N;
$L[0] = 0; $L[1] = 0;
$start = 2;
$t0 = time;
while($start<$N) {
if($L[$start]==0) { $start++; next; }
for($i=$start*2;$i<$N;$i+=$start) { $L[$i] = 0; }
$start++;
}
print "time: ".(time-$t0)."\n";

for($i=0;$i<$N;$i++) {
# print $i." " if($L[$i]==1);
}

[vilfred@mobile100 vilfred]$ ./eratos.pl
panic: malloc at ./eratos.pl line 3.
[vilfred@mobile100 vilfred]$

для $N = 100000050;
[vilfred@mobile100 vilfred]$ time ./eratos.pl
Out of memory!

real 0m1.752s
user 0m1.330s
sys 0m0.420s
[vilfred@mobile100 vilfred]$

для $N = 10000050;
[vilfred@mobile100 vilfred]$ time ./eratos.pl
time: 34

real 0m38.773s
user 0m38.170s
sys 0m0.400s
[vilfred@mobile100 vilfred]$

А в первом случае через интервалы могу хоть както за _конечное_ время получить простые числа без дополнительных библиотек для работы с очень большими числами (которых на www.cpan.org некоторое количество есть)

первый пример можно запустить в фон: nohup ./yy.pl 1>stdout 2stderror &
и забыть о нем на год (если машину не перегружать)... он потихоньку да и досчитает.

А с приведенной реализацией решета Эратосфена (по другому просто не знаю как писать, может и можно) приходится в памяти строить массив данных... и тут для работы критичны возможности машины.

По поводу нечетности, дык это, если число четно, то оно заведомо непростое, разве нет? (иными словами это не учитывается)...

вообще, конструкции 0 .. 1000000000 (которые передаются подпрограммам) это массивы с 1000000000-1 значениями. Там в интервале 1000000000 .. 1000000050, насколько я понял, идет сравнение с полным числовым рядом (и какова скорость?). Т.е. с миллиардом. то что там интервал в 50 стоит - ничего не значит... там не по 50 сравнение вовсе идет.

p.s. работать с inodes под linux я не умею...

p.s.s. а гденнить есть список простых чисел? Эти два алгоритма проверить.

Цитата

По поводу нечетности, дык это, если число четно, то оно заведомо непростое, разве нет?
(иными словами это не учитывается)...

Тогда, простите, за какой же радостью Вы в вашей программе резервируете для этих чисел ячейки в решете?! А потом еще удивляетесь, что malloc в панике!

Цитата

вообще, конструкции 0 .. 1000000000 (которые передаются подпрограммам) это массивы с
1000000000-1 значениями.

Кто ж Вас заставляет передавать 0..1000000000?

Цитата

Там в интервале 1000000000 .. 1000000050, насколько я понял, идет сравнение с полным числовым рядом (и какова скорость?). Т.е. с миллиардом. то что там интервал в 50 стоит - ничего не значит... там не по 50 сравнение вовсе идет.

Нет, Вы поняли совершенно неправильно!
Ваш полный перебор требует порядка C*N*sqrt(M), где C - константа, N - ширина интервала, M - максимльное значение. Правильно написанное решето требует C'*sqrt(M)*log(N) операций.
При этом перебор действительно может отработать быстрее, если C'/C > N/log(N); ну и что с того? Если Вы возьмете ширину интервала не 50, а 50000, Ваш перебор отработает в 1000 раз медленнее, а решето замедлится менее чем в 7 раз. А можно взять не 50000, а весь миллиард. Поэтому Ваше решение как раз ни в какой мере не является общим - оно годится только для узких интервалов. И вообще, подобным образом доказывать, что перебор до корня работае быстрее решета - все равно, что утверждать, что велосипед быстрее самолета, мотивируя это тем, что на велосипеде рано или поздно можно приехать на дачу, а самолет там попросту завязнет в навозе при посадке! :-)

Цитата

p.s. работать с inodes под linux я не умею...

Для того, чтобы соптимизировать под swap, это не требуется. Для этого поступают так:
1. Массив разбивают на блоки (размер блока выбирается так, чтобы два блока гарантированно
помещался в физическую память).
2. Вместо того, чтобы для каждого простого числа заполнять решето его делимыми до конца,
вначале полностью заполняется первый блок, затем - второй и т.д.
Устроено просто, работает эффективно, только C' возрастает (применял в поиске совершенных чисел - не хватало оперативки для вычисления пятого "решетом", а перебор делителей в этой задаче просто не котируется - тогда я еще не знал, что все четные описываются простой формулой, а нечетных еще в глаза никто не видел и не исключено, что их нет - во всяком случае, доказано, что гипотетическое нечетное совершенное неразложимо в произведение восьми или менее простых).

Цитата

p.s.s. а гденнить есть список простых чисел? Эти два алгоритма проверить.

В интернете точно есть, и не один вариант. На работе ребята как-то скачивали для тестирования. :-)

только я не знаю как на perl'e это написать :)
Идея в следующем. Есть некий прцесс, читающий из stream'a числа и выдающий новый stream по следующему правилу: первое число входного stream'a объявляется простым, а на выход подаются все числа из входного потока не кратные первому. Если построить pipeline таких процессов и на вход первому дать 2..N, то в результате получишь что надо. Правда, для этого решения - чем больше процессоров тем лучше, но память не так вожна.

Вы считаете себя слишком занятым для правильного цитирования? И полагаете, что модераторы должны заниматься этим вместо вас?

гм, просто скопировать текст выделением в мозилловский почтовик, где оно автоматом расставит квотирование быстрее, чем руками вбить

Цитата

some text

. 12 символов против трех кликов мышкой.

я про один проценссор говорил. ну да ладно. а perl - да ,он в 10 раз медленнее чем c/c++

Цитата

Я параллелю задачу и мне жить дешевле, форкнулся на 200 прцессов на p100, сиди и жди.

Ну и получил 200 независимых процессов. Вот для этого количество процессоров еще более критично, чем для моего алгоритма.