Нахождение простых чисел без деления

[venco]

Какая разница как оно называется. В чём отличие кроме названия и скорости?
Кстати, решето - тоже сепаратор.

[iig]

Этот алгоритм по сути проверка на делимость, здесь также можно выбирать только нечетные или 6*к+-1, ограничиваться до корня и т.д., зато нет деления.
Если кто-то хочет называть решетом- нехай себе, абы не в печку.

[iig]

Прошу еще раз обратить внимание на небольшое редактирование темы в начале, если кто не понял.

[venco]

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

[iig]

venco в сообщении #228867 писал(а):

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

Опять вы о скорости, предлагаю на Паскале посоревноваться конкрентно до 100 000 или более и сравнить. Ваша привязанность к предварительным оценкам понятна, но я предлагаю на практике убедиться. Паскаль, без вставок Ассемблера я выбираю потому как почти за 20 лет привык, правда, последнее время Маткад устраивает - в пределах моей точности и скорости.
В общем, если не против, я согласен на публичную дуэль, чтобы определить рамки эффективности.
В общем, предлагаю найти Н=1000,..1000000 простое число по договоренности.
При этом предъявлять прогу на Паскале с комментариями пжлт, без фокусов, чтобы оба поняли и у себя на компе и у других выполнили и сравнили. Версию паскаля указать, у меня все есть даже фри, но делфу не ставил, так что давай попроще.

[venco]

У меня вообще паскаля нет. Если получится gcp поставить, попробую.

[iig]

Могу прислать ТП7 - 1мБ, сам тоже на нем буду.

[venco]

Сделал на GNU Pascal.

Используется синтаксис Pascal

Program primes;

{
 Get current time as precise as possible.
 You can replace this function with anything suitable on your compiler.
 This version reads CPU clock counter with RDTSC instruction.
 It's then divided by the clock frequency - replace it with frequency of your CPU.
 I have 2.4 GHz Intel Core 2 processor.
 }
Function FineTime : Real;
Var
   frequency : Real = 2.4e9; { CPU frequency }
   clock     : Cardinal attribute (Size = 64);
begin
   asm volatile("rdtsc" : "=A" (clock));
   FineTime := clock / frequency;
end;

{ Count number of primes up to n using simple sieve of Eratosthenes. }
Function prime_count1(n : Integer) : Integer;
Type
   TSieve = Array[0..999999999] of Boolean;
   PSieve = ^TSieve;
Var       
   i           : Integer;
   j           : Integer;
   prime_count : Integer;
   prime       : PSieve; { dynamically allocated array for the sieve }
begin
   GetMem(prime, (n+1)*sizeof(Boolean)); { allocate the sieve array }
   FillChar(prime^, (n+1)*sizeof(Boolean), True); { fill it with ones }
   prime_count := 0;
   for i := 2 to n do
   begin
      if prime^[i] then { next prime found }
      begin
         Inc(prime_count);
         { mark all multiplies as non-primes: }
         j := i*2;
         while j <= n do
         begin
            prime^[j] := False;
            Inc(j, i);
         end;
      end;
   end;
   FreeMem(prime, (n+1)*sizeof(Boolean)); { free sieve array }
   prime_count1 := prime_count;
end;

{ run prime counting function and determine its runtime }
Procedure test1(n : Integer);
Var
   count : Integer;
   time  : Real;
begin
   time := FineTime();
   count := prime_count1(n);
   time := FineTime() - time;
   WriteLn('Number of primes up to ',n,' - ',count,'   time spent: ',time:0:3,' secs');
end;
   
begin
   test1(100000);
   test1(1000000);
   test1(10000000);
   test1(100000000);
end.
 

Команда компиляции: gpc -O3 -o primes2p.exe primes2p.pas
Результаты:
Number of primes up to 100000 - 9592 time spent: 0.001 secs
Number of primes up to 1000000 - 78498 time spent: 0.008 secs
Number of primes up to 10000000 - 664579 time spent: 0.408 secs
Number of primes up to 100000000 - 5761455 time spent: 5.770 secs

Я имплементировал также ваш алгоритм (как я его понял) и вот его результаты для сравнения:
Number of primes up to 100000 - 9592 time spent: 3.002 secs

[iig]

Уважаемый оппонент, я решил отказаться от споров.
Мой алгоритм проверяет делимость чисел, при этом при каждом акте проверки делить не надо, а всего лишь добавить единицу!
В остальном ничем не отличается от проверки на делимость и ничего общего не имеет с решетом.
Спасибо за внимание.

[iig]

venco в сообщении #228867 писал(а):

А тривиальное деление быстрее потому, что делим только до первого нуля, а у вас приходится считать все остатки до конца.

Можно не считать до конца все остатки - обнаружив 0 перейти к следующему числу, только для вычисления остатков делать коррекцию, добавляя не 1, а больше по модулю.
Примерно так: от последнего простого помним сколько добавить и проверяем, а вот если обнаружится простое, то коррекцию действительно придется ко всем ранее обнаруженным применить.
Это только наброски, конкрентно можно уточнить.
Впрочем, не стоит так изгаляться, проще добавлять по 1 ко всем по ихним модулям.

[iig]

Цитата:

Const Rmax = 9;
Var
P:array [1..Rmax] of integer;{Prime numbers}
R:array [1..Rmax] of integer;{Rests}
Num,Nmax,N :integer;
Pyes :boolean;
begin
writeln('Prime numbers search by [e-mail] Ver 13.09.2009');
Num:=2;P[1]:=2;Nmax:=1;R[1]:=0;
repeat
inc(Num); Pyes:=true;
write(Num:6);
for N:=1 to Nmax do
begin
inc(R[N]);
if R[N] = P[N] then begin R[N]:=0; Pyes:=False; end;
Write(R[N]:4);
end;
if Pyes then begin inc(Nmax);P[Nmax]:=Num;R[Nmax]:=0;write(Num:4,'!');end;
writeln;
until Nmax = Rmax;
write('Enter for exit');Readln;End.

[iig]

Комментарий, по русски пояснение:
Деление заменяется добавлением единицы по модулю - самый примитивный вариант, но интересно, как этот алгоритм себя проявит в скорости типа найти все первые миллион или меньше миллиона.
Я полагаю, используя ассемблер в критических вставках, можно посоревноваться.
Эта программа демонстрационная, никаких приемов эффективности,
только чтобы алгоритм показать понятней.
Послал на сайт который взял на себя простые числы во всем мире
http://primes.utm.edu/
оне мудаки не ответили, хотя на моем инглише вроде ясно пояснил; ну и хрен с ними , потом сами пожалеют.
Учите русский. Это в перспективе будет второй язык после китайского