Форум программистов, компьютерный форум, киберфорум
Наши страницы

Free Pascal

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 26, средняя оценка - 4.85
galileopro
Пробующий
184 / 97 / 1
Регистрация: 28.04.2009
Сообщений: 1,040
#1

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

04.05.2009, 21:43. Просмотров 3397. Ответов 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
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Алгоритм Эратосфена (Free Pascal):

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

Алгоритмом Решето Эратосфена найти четвёрки меньших N простых чисел, принадлежащих одному десятку - Free Pascal
Здравствуйте. Условие задачи в названии темы. Здесь, на форуме, нашлось вот такое решение (автор - volvo) const N = 2000; ...

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

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

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

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

10
Puporev
Модератор
54019 / 41652 / 14731
Регистрация: 18.05.2008
Сообщений: 97,916
04.05.2009, 21:47 #2
Эристофена это кто?
1
Sergei
1446 / 713 / 41
Регистрация: 22.04.2008
Сообщений: 1,610
04.05.2009, 21:50 #3
Первый раз слышу про алгоритм Эристофена есть алгоритм Эратосфена но ни как не Эристофена.
0
galileopro
Пробующий
184 / 97 / 1
Регистрация: 28.04.2009
Сообщений: 1,040
04.05.2009, 21:52  [ТС] #4
Ученый.

Добавлено через 1 минуту 7 секунд
Ну а код нормальный, кто-нибудь пробовал тестировать?
0
Puporev
Модератор
54019 / 41652 / 14731
Регистрация: 18.05.2008
Сообщений: 97,916
04.05.2009, 21:52 #5
Ученый.
Не ученый, а просто читать умеет, у Вас же написано
Такой метод нахождения простых чисел называется решетом Эратосфена.
0
Sergei
1446 / 713 / 41
Регистрация: 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
Модератор
54019 / 41652 / 14731
Регистрация: 18.05.2008
Сообщений: 97,916
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 / 1
Регистрация: 28.04.2009
Сообщений: 1,040
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 / 1
Регистрация: 28.04.2009
Сообщений: 1,040
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
Привет! Вот еще темы с ответами:

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

Линейный алгоритм, Алгоритм с ветвлениями, Циклический алгоритм Линейный алгоритм - Pascal
Линейный алгоритм, Алгоритм с ветвлениями, Циклический алгоритм Линейный алгоритм 1. Объясни, что будет напечатано программой Program...

Из множества целых чисел [1.1000] методом решета Эратосфена получить множество простых чисел и вывести их на экран - Free Pascal
Из множества целых чисел методом решета Эратосфена получить множество простых чисел и вывести их на экран.

Вложеные циклы.Составить программу вывода на экран простых чисел из первых N натуральных чисел используя решето Эратосфена. - Pascal
Составить программу вывода на экран простых чисел из первых N натуральных чисел используя решето Эратосфена. Решить задачу с...


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

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

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