С наступающим Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы
Free Pascal
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.68/19: Рейтинг темы: голосов - 19, средняя оценка - 4.68
galileopro
Пробующий
184 / 97 / 10
Регистрация: 28.04.2009
Сообщений: 1,104
1

Алгоритм Эратосфена

04.05.2009, 21:43. Просмотров 3491. Ответов 10
Метки нет (Все метки)

Коснусь вопроса поиска простых чисел. Был вопрос от 13Legion как найти 24 простых 6-значных числа. Так вот делается это так:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
program Project2;
uses
  SysUtils;
const N=200000; //вместо 10 запишите число - верхнюю границу поиска
 
var 
a : array [1..N] of boolean; 
x,y,kol : integer; 
 
 
begin 
a[1] := true; 
for x:=2 to N do a[x] := true; 
 
for x:= 2 to N div 2 do
for y:= 2 to N div x do 
a[x*y] := false;
 
kol:=1;
for x:= 100000 to 100330 do
if a[x] then begin
       writeln('x[',kol,']= ',x);//выводим данные в столбец
       inc(kol);
       end;
readln; 
end.
Вот теория вопроса:
В последовательности чисел 2,3, ... , n последовательно вычеркиваем каждое второе число после 2. Первое незачеркнутое число простое (3). Далее вычеркиваем каждое третье число после 3. Первое незачеркнутое число простое (5). Затем вычеркиваем каждое пятое число после 5 и т.д. до тех пор, пока не дойдем до числа, большего корня из n (известно, что если целое положительное число n неравное 1 не делится ни на одно положительное простое число, не большее корня из n то оно простое). Все числа, которые остаются, простые. Такой метод нахождения простых чисел называется решетом Эратосфена.
Процедура заполняет массив P простыми числами меньшими n, элемент массива является последним, если следующий за ним элемент равен 0
На экран я вывожу только 24 числа но можно и все тогда вместо
kol:=1;
for x:= 100000 to 100330 do
if a[x] then begin
writeln('x[',kol,']= ',x);//выводим данные в столбец
inc(kol);
end;
Пишите
for x:= 1 to N do
if a[x] then begin
writeln(x, ' ');//выводим данные в строчку
end;

Добавлено через 4 минуты 48 секунд
Еще раз напомню, что это поиск простых чисел именно методом решета Эристофена и числа программа ищет от 0 до N просто на экран выводит 24 первых 6-значных числа. Если хотите вывести все числа то поменяйте немного код как сказано ранее. Приятного использования.
1
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.05.2009, 21:43
Ответы с готовыми решениями:

Дано натуральное число n. Найти все меньшие n простые числа, используя решето Эратосфена
4. Дано натуральное число n (n≥2). Найти все меньшие n простые числа, используя...

Алгоритмом Решето Эратосфена найти четвёрки меньших N простых чисел, принадлежащих одному десятку
Здравствуйте. Условие задачи в названии темы. Здесь, на форуме, нашлось вот...

С помощью алгоритма Решето Эратосфена найти четвёрки меньших N простых чисел, принадлежащих одному десятку
Условие задачи:дано натуральное число N. С помощью алгоритма "решето...

Решето Эратосфена
Я бы хотела спросить у вас, как можно ускорить алгоритм "решето Эратосфена" до...

Решето Эратосфена
Ребят, помогите решить задачу. В программировании профан( Задача нужна в...

10
Puporev
Модератор
55507 / 42595 / 29444
Регистрация: 18.05.2008
Сообщений: 100,754
04.05.2009, 21:47 2
Эристофена это кто?
1
Sergei
1454 / 721 / 103
Регистрация: 22.04.2008
Сообщений: 1,610
04.05.2009, 21:50 3
Первый раз слышу про алгоритм Эристофена есть алгоритм Эратосфена но ни как не Эристофена.
0
galileopro
Пробующий
184 / 97 / 10
Регистрация: 28.04.2009
Сообщений: 1,104
04.05.2009, 21:52  [ТС] 4
Ученый.

Добавлено через 1 минуту 7 секунд
Ну а код нормальный, кто-нибудь пробовал тестировать?
0
Puporev
Модератор
55507 / 42595 / 29444
Регистрация: 18.05.2008
Сообщений: 100,754
04.05.2009, 21:52 5
Ученый.
Не ученый, а просто читать умеет, у Вас же написано
Такой метод нахождения простых чисел называется решетом Эратосфена.
0
Sergei
1454 / 721 / 103
Регистрация: 22.04.2008
Сообщений: 1,610
04.05.2009, 21:56 6
Вот код программы также реализующий алгоритм Эратосфена
но пригодного для отыскания большего числа простых чисел поскольку его требования к памяти корень квадратный из m- количество простых чисел.
Время выполнения программы m в степени 3/2
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
program eratosphen;
 
uses
        Crt;
 
const
        n = 20;
        m = n * n;
 
var
        p, s, i, j, k: Word;
        accept: Boolean;
        prime: array[1..m - 1] of Word;
        mult: array[1..n - 1] of Word;
        old_mode: Integer;
 
begin
        ClrScr;
        prime[1] := 2;
        p := 2;
        k := 1;
        s := Sqr(prime[1]);
        for i := 2 to m - 1 do
        begin
                repeat
                        Inc(p);
                        if s <= p then
                        begin
                                mult[k] := s;
                                Inc(k);
                                s := Sqr(prime[k]);
                        end;
                        accept := True;
                        for j := 1 to k - 1 do
                        begin
                                if mult[j] < p then
                                        mult[j] := mult[j] + prime[j];
                                accept := (mult[j] > p);
                                if not accept then
                                        Break;
                        end;
                until accept;
                prime[i] := p;
        end;
        WriteLn;
        WriteLn;
        old_mode := lastmode;
        TextMode(CO80 + font8x8);
        for i := 1 to 10 do
                Write(i:8); WriteLn;
        TextColor(Yellow);
        for i := 1 to m - 1 do
                Write(prime[i]:8);
        WriteLn;
        WriteLn;
        TextColor(LightGray);
        Write('Ќ*¦¬ЁвҐ <Enter>');
        ReadLn;
        TextMode(old_mode);
end.
0
Puporev
Модератор
55507 / 42595 / 29444
Регистрация: 18.05.2008
Сообщений: 100,754
04.05.2009, 21:56 7
a[1] := true;
for x:=2 to N do a[x] := true;
А можно и так
a[1]:=true; a[2]:=true; a[3]:=true;...... a[n]:=true;
0
galileopro
Пробующий
184 / 97 / 10
Регистрация: 28.04.2009
Сообщений: 1,104
04.05.2009, 22:18  [ТС] 8
Спасибо за советы. Выложу, на всякий случай, поправленный код.
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
program Erastofen;
uses
  SysUtils;
const N=10; //вместо 10 запишите число - верхнюю границу поиска
var 
a : array [1..N] of boolean; 
x,y : integer; 
begin 
for x:=1 to N do a[x] := true; 
 
for x:= 2 to N div 2 do
for y:= 2 to N div x do 
a[x*y] := false;
 
for x:= 1 to N do 
if a[x] then writeln(x, ' ');//выводим данные в строчку
readln; 
end.
Добавлено через 13 минут 49 секунд
Кстати словом "Ученый" я никого обидеть не хотел, а просто отвечал на вопрос, ведь Эратосфена - полюбому ученый. Спасибо за код, Sergei. Я постараюсь поискать и другие методы нахождения простых чисел, если анйду что-либо более оптимизированного, чем Ваш пример, то напишу обязательно.
0
13Legion
1 / 1 / 0
Регистрация: 01.05.2009
Сообщений: 20
04.05.2009, 23:12 9
Вот код решения, как мы делали, программа ищет 23 простое шести разрядное число.
Но как справедливо замечено, здесь требуется компилятор посильнее..., типа Free Pascal PRO.

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Program resheto;
uses crt;
const
  n = 999999; { Это можно и уменьшить, взят граничный случай}
var
  a: array[1 .. n] of  longint; {создаём массив от 1 до 999999 }
  i, j, s, count: longint;
 
begin
  for i := 1 to n do a[i] := i; {заполняем массив }
  a[1] := 0;
 
  for s := 2 to pred(n) do begin 
    if a[s] <> 0 then begin
      j := s * 2;
      while j < n do begin
        a[j] := 0;
        j := j + s;
      end;
    end;
  end;
 
  count := 0;
  i := 100000;
  while count < 26 do begin
    if a[i] > 0 then inc(count);
    inc(i);
  end;
  writeln(a[i - 1]);
end.
1
galileopro
Пробующий
184 / 97 / 10
Регистрация: 28.04.2009
Сообщений: 1,104
05.05.2009, 19:44  [ТС] 10
У тебя код не оптимизирован главным образом по двум причинам:
1. Слишком много памяти.
2. Достаточно много машинного времени.
Памяти много так как там объявляется массив из шестизначных чисел (longint). Но уже давно придумано для этой задачи использовать массив из логических переменных (всего-то 1 бит) и просто помечать простые числа флажками. А насчет машинного вермени там нужно посчитать
{ Это можно и уменьшить, взят граничный случай}
Этот граничный случай, так как там, я подозреваю, далеко не 999999 а что-то вроде 101000 например а то и меньше.
1
13Legion
1 / 1 / 0
Регистрация: 01.05.2009
Сообщений: 20
06.05.2009, 00:05 11
galileopro, Но у меня всё же правильно считает а это главное. Всё же спасибо за замечание, учтём.

Добавлено через 34 секунды
И если можно асю свою кинь мне в личку, спишемся.
0
06.05.2009, 00:05
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.05.2009, 00:05

Нахождение суммы элементов в решете Эратосфена
В данный код программы, строящей решето Эратосфена до необходимого числа,...

Поиск простых чисел методом решета Эратосфена.
Помогите пожалуйста решить: 1)Составить процедуру, которая находит все...

Линейный алгоритм, Алгоритм с ветвлениями, Циклический алгоритм Линейный алгоритм
Линейный алгоритм, Алгоритм с ветвлениями, Циклический алгоритм Линейный...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru