Алгоритм "решета Эратосфена", Нахождение простых чисел в натуральном ряду Опции

[Developer]

Георгий обещал за десять минут написать программу для нахождение простых чисел в натуральном ряду. Пока пишет, я приведу пару реализаций алгоритма.
Вот алгоритм:
1 В последовательности чисел 1,2,3,...,n первые два числа простые.
2 Последовательно вычёркиваем каждое второе число после 2, тогда первое незачёркнутое (3) - простое число.
3 Затем вычёркиваем каждое третье после 3, тогда первое незачёркнутое (5) - простое число.
4 Теперь вычёркиваем каждое пятое после 5, тогда первое незачёркнутое (7) - простое число.
5 Продолжаем вычёркивание для 7, 11 и т.д., пока не дойдём до числа, большего .
6 Все незачёркнутые числа - простые.
Количество простых чисел в ряду не превышает , если или , если .

А вот пример на турбо-бейсике:

Код

'=====================================================
'   This  program demonstrates the SIEVE algorithm of determining prime numbers.
'   The algorithm is often used in benchmarking the speed of compilers.
'                                        
'   In order to run this program do the following:
'     1. Load Turbo Basic by typing TB at the DOS prompt.
'     2. Load the file SIEVE.BAS from the Load option of the File pulldown menu.
'     3. Select Run from the Main menu
'=====================================================
' The Classic Sieve of Eratosthenes Benchmark
'
DEFINT A-Z
DIM Flags(8190)

CLS
PRINT "Sieve - 25 iterations"
X# = TIMER

FOR Iter = 1 TO 25
  Count = 0
  FOR I = 0 TO 8190
    Flags(I) = 1
  NEXT I
  FOR I = 0 TO 8190
    IF Flags(I) THEN
      Prime = I + I + 3
      K = I + Prime
      WHILE K <= 8190
        Flags(K) = 0
        K = K + Prime
      WEND
      Count = Count + 1
'    PRINT prime; : PRINT " ";      
    END IF
  NEXT I
NEXT Iter

XX# = TIMER
PRINT USING "#### primes in ##.### seconds";count;XX#-X#

END

А попозже приведу ещё одну на турбо-паскале.

[Nataly-Mak]

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

А для алгоритма Сундарама у вас есть программа?
Я уже писала здесь (в теме “Взаимно простые числа”) о своей рукописи книги “Компьютер решает головоломки”. В этой рукописи есть глава “Простые числа”, а в главе есть программка для алгоритма Сундарама, которая была написана ещё для допотопной ЭВМ на языке BASIC. С помощью этой программы я получила ряд простых чисел в интервале от 5 до 1000. Сейчас проверила эту программу, она прекрасно работает. Вот она:

Код

5 PRINT "VVEDITE M"
7 INPUT M
10 FOR I = 5 TO M STEP 2
15 B = I: A = (B - 1) / 2
17 C = A - 1
20 FOR N = 1 TO C
25 K = (A - N) / (1 + 2 * N)
30 IF INT(K) = K THEN 40
35 NEXT N
37 PRINT B
40 NEXT I
45 PRINT
50 END

Введите в программу любое натуральное , до которого вы хотите получить простые числа, и программа их вам выдаст (конечно, в разумных пределах). В интервале от 5 до 1000 программа выдала ряд простых чисел за 3 секунды.





Сообщение отредактировал Nataly-Mak - 21.5.2009, 15:14

[Developer]

Я не математик, поэтому простыми названиями алгоритмов (например, алгоритм Сундарама) меня смутить невозможно, поскольку я просто не знаю, что это такое.
Русским языком изложите этот алгоритм, Nataly-Mak (в Вашем нике я обнаружил пару пробелов, ASCII код 32), а программу на его основе сделать недолго.

[Developer]

Проверил Вашу программу, Nataly-Mak.
1 Она не выводит первые три простых числа 1,2,3.
2 "Работает" то есть выводит правильные результаты и при M>1000.
Я задал ей M=1е6.
Программа отработала несколько минут, окончания работы я ждать не стал, поскольку знаю, что простых чисел должно быть не меньше 250001 (на дисплее в это время мелькали: ...72251, 72253, 72269, 72271, 72277, 72287, 72307,...).
Поделитесь алгоритмом Сундарама.

[Nataly-Mak]

Поделитесь алгоритмом Сундарама.

С удовольствием!
Цитата из моей рукописи:
”Очень оригинальное ”решето” для отсеивания простых чисел придумал индийский математик Сундарам. Это решето представляет собой таблицу, состоящую из бесконечного количества бесконечных арифметических прогрессий, причём каждый член первой прогрессии начинает новую прогрессию. Разностями прогрессий являются все нечётные числа, начиная с 3.
Первые три строки таблицы Сундарама:

Код

4  7  10  13  16  19  22  25  28  31  34  37 40  43  46  49...
7  12  17  22  27  32  37  42  47  52  57  62  67  72  77  82  87 ...
10  17  24  31  38  45  52  59  66  73  80  87  94  101  108  115 ...

В чём же секрет этого ” решета ”? Оказывается, если какое либо число содержится в таблице Сундарама, то число будет составным, если же число не попало в таблицу Сундарама, то число будет простым. Например, числа 5 нет в таблице Сундарама, значит число 2 * 5 + 1 = 11 – простое; число 7 есть в таблице Сундарама, следовательно, число 2 * 7 + 1 = 15 – составное”.
Вот и весь алгоритм. Загляните ещё в тему ”Взаимно простые числа” (на этом форуме), там по этому поводу тоже кое-что написано.
Помню, что Георгий в личной переписке писал мне, что его программа для алгоритма Сундарама есть в Википедии. Непонятно, чего-то он сейчас притих

Сообщение отредактировал Nataly-Mak - 22.5.2009, 8:08

[Георгий]

http://ru.wikipedia.org/wiki/Решето_Сундарама

Эту статью я писал.

[Developer]

Помню, что Георгий в личной переписке писал мне, что его программа для алгоритма Сундарама есть в Википедии. Непонятно, чего-то он сейчас притих :)

Не буди Лихо, пока оно тихо...

[Nataly-Mak]

Не буди Лихо, пока оно тихо...

Спасибо за мудрый совет! Учту
Кстати, я немножко фольклорист.
Так вы всё поняли с алгоритмом Сундарама? Можно сделать программу так, что она будет выдавать простые числа в заданном интервале, например, в интервале (999, 2000). Главное, начало цикла по I задать с нечётного числа, этот цикл идёт с шагом 2, проверяются только нечётные числа. Понятно, что все чётные числа составные.
Я вот собралась написать математическую новеллу "Простые числа". Приглашаю вас и ещё VAL в соавторы, потому что я здорово отстала от современных достижений в этой области.

[Developer]

Спасибо за приглашение, Nataly-Mak, но боюсь, что в отличие от Вас, я в этой области "вообще не догоняю"...
Лучше приведу программу на паскале, как и обещал (компилятор Turbo-Pascal 5.5; программа будет исполняться и на других версиях TP, BP и вплоть до Delphi 7):

Код

Program Sieve;
  Uses Crt,Dos;
  Label 1;
  Const
    Nmin    = 0;
    Nmax    = 32767;
    Pmax    = 3903;
  Var
    n,n_Pr  : Integer;
    i,j,k   : Word;
    Error   : Word;
    s,r     : Real;
    Row,Col : Byte;
    Prime   : Array[1..Pmax] of Word;
  Procedure Beep;        {Sound signal of input error}
    Begin
      {Sound(220); Delay(40000); NoSound}
      For i:=1 To 5 Do Begin Write(#7); Delay(4000) End
    End;
  Procedure Position;      {Returns cursor location}
    Begin
      Row:=WhereY; Col:=WhereX
    End;
  Procedure Trtmnt;        {Input error treatement}
    Begin
      Error:=1; Beep;
      Write('Error! Repeat iputing!');
      GoToXY(Col,Row); ClrEol
    End;
  Begin
    Write('N = '); Position;
    Repeat
      Error:=0; {SI-} {SR-} GoToXY(Col,Row);
      Readln(n);
      If (n <= Nmin) Or (n > Nmax) Or (IOResult<>0)
        Then Trtmnt
      Else ClrEol; {SI+} {SR+}
    Until ((n > Nmin) And (n <= Nmax)) And (Error=0);
    If (n > 200)
      Then r:=Int(n/(Ln(n)/Ln(10)-2)+1)
      Else r:=Int(1.6*n/Ln(n)/Ln(10)+1);

    Prime[1]:=1; Prime[2]:=2; Prime[3]:=3; j:=3;
    For k:=3 To n Do
      Begin
        If (k/2 <> Int(k/2)) Then
          Begin
            i:=2; s:=Sqrt(k);
            Repeat
              Inc(i);
              If (Prime[i] > s) Then
                Begin
                  Prime[j]:=k; Inc(j); GoTo 1;
                End
            Until(Int(k/Prime[i])*Prime[i] = k)
          End;
        1:
      End;
    WriteLn('Prime numbers less then ',n,' are equal:');
    n_Pr:=0;
    Repeat
      Inc(n_Pr);
    Until(n_Pr = j-1);
    For i:=1 To n_Pr Do
      Begin
        If Prime[i]=0 Then Exit;
        Write('P(',i,')=',Prime[i],' ');
      End
  End.

Сообщение отредактировал Developer - 22.5.2009, 9:18

[Георгий]

Хорошая прога! Проверено - мин нет!

[Developer]

Георгий! А Вы так же красиво оформляете программы?
Я комментарии специально не вставлял, чтобы появились вопросы.
Да вот незадача:
- делаю прогон для n=8190 программы на бейсике, получаю 1899 простых чисел, последнее имеет значение 16381. Парадокс? Абсурд? Где ошибка?
- делаю прогон для n=8190 программы на паскале, получаю всего 1028 простых чисел, последнее имеет значение 8179. Похоже на правду;
- делаю прогон для n=8190 программы на бейсике, которую представила Nataly-Mak, получаю всего 1025 простых чисел, последнее имеет значение 8179. C учётом того, что первые простые числа 1,2,3 эта программа не выявляет, тоже похоже на правду.

[Георгий]

Интересную задачу подкинули! Ночью вплотную займусь ею. Вдруг здесь аж две-три истины?

Сообщение отредактировал Георгий - 22.5.2009, 13:30

[Developer]

Да какие там истины? Логическая ошибка в алгоритме...
Вам "скинуть" борландовский Turbo-Basic?
Всего три файла:
- tb.exe - 204317 Bytes
- tbconfig.tb - 886 Bytes
- tbhelp.tbh - 41029 Bytes.
 Tb.zip ( 136.46 килобайт ) Кол-во скачиваний: 34


Сообщение отредактировал Developer - 22.5.2009, 15:05

[Inspektor]

Я когда-то оба эти алгоритма реализовывал на С++, для кого и зачем писал не помню, ясно только что задания были на списки . В обеих прогах есть таймер, который говорит, что решето Эратосфена во много раз эффективнее.
Эратосфен:
исходник  List.rar ( 648 байт ) Кол-во скачиваний: 51

экзешник  List.rar ( 3.01 килобайт ) Кол-во скачиваний: 39

Сандурам(или как-то так)
исходник  main.rar ( 843 байт ) Кол-во скачиваний: 27

экзешник  Sundaram___.rar ( 3.22 килобайт ) Кол-во скачиваний: 21

Пришлось всё запаковать а то форум не пускает.
З.Ы. В википедии алгоритм этого сандурдома не верно описан.

Сообщение отредактировал Inspektor - 22.5.2009, 21:11

[Георгий]

Задача - делать нечего. Меньше чем за минуту пишу прогу на Maple12

s:=0:for i from 1 to 8190 do if isprime(i)=true then s:=s+1;fi;od;print(s):

Правильный ответ 1027. Время счета - мгновение ока.

В http://mindspring.narod.ru/math/ega/Liv/Zagier.htm приведена таблица количества пристых чисел до 10 миллиардов. Я проверил для миллиона - совпадение полное: 78498 . Время счета 2,1 с.

Сообщение отредактировал Георгий - 23.5.2009, 20:03

[Inspektor]

Задача - делать нечего. За 1 минуту пишу прогу на Maple12

s:=0:for i from 1 to 8190 do if isprime(i)=true then s:=s+1;fi;od;print(s):

Ответ 1027. Время счета - менее секунды. ( в качестве контроля - для первых 100 чисел простых 25).

это не прога, а скрипт. В математике ещё проще:

Код

PrimePi[8190]

[Hottabych]

А простые числа между и найти как? (шутка)

[Inspektor]

я давно отошел от таких убожеств, как всякие Turbo и Quickи (и даже от C++ c Ассемблерами).

Точнее "уже не надеюсь освоить си и ассемблер"

[Георгий]

На Ассемблере я программировал аж в 1973 году. Вот интересно - сколько же Вам лет было?

[Inspektor]

На Ассемблере я программировал аж в 1973 году. Вот интересно - сколько же Вам лет было?

-16 лет. Как же вы могли так деградировать, с асма до скриптов...