Login
Поиск простого числа
NEW 08.11.06 07:54
Задача: найти простое число по его порядковому номеру в последовательности простых чисел, вот такая прога. Не хочет работать. Пожалуйста, тыкните в ошибку!
program prostoe;
const n=30000;
var
a:array[1..n] of integer;
chs:integer;
sum,num,i,b:integer;
function prov (c:integer):boolean;
var s:byte;
del:integer;
begin
s:=0;
for del:=2 to c do
begin
if c mod del=0 then inc(s);
if s<>0 then break;
end;
if s=0 then prov:=true;
end;
begin
readln(chs);
num:=1;
for b:=1 to chs do
begin
if prov(num)=true then a:=num;
inc(num);
end;
readln;
end.
Проблема в том, что массив при пошаговой проверке не заполняется, только первый элемент становится равным единице и все.
program prostoe;
const n=30000;
var
a:array[1..n] of integer;
chs:integer;
sum,num,i,b:integer;
function prov (c:integer):boolean;
var s:byte;
del:integer;
begin
s:=0;
for del:=2 to c do
begin
if c mod del=0 then inc(s);
if s<>0 then break;
end;
if s=0 then prov:=true;
end;
begin
readln(chs);
num:=1;
for b:=1 to chs do
begin
if prov(num)=true then a:=num;
inc(num);
end;
readln;
end.
Проблема в том, что массив при пошаговой проверке не заполняется, только первый элемент становится равным единице и все.
NEW 08.11.06 09:57
in Antwort taksos 08.11.06 07:54
NEW 08.11.06 09:59
in Antwort taksos 08.11.06 07:54, Zuletzt geändert 08.11.06 10:45 (scorpi_)
Это что за бредовый алгоритм? Посмотри в инете решето Эратоcфена, и перепиши программу соответствующим образом.
NEW 08.11.06 10:07
in Antwort scorpi_ 08.11.06 10:01
Эээ... все никак не привыкнешь, что Я, при подобных вопросах, обычно не даю прямого ответа, но вынуждаю подумать... 
Странно, что компайлер на этой строке не матюгнулся...
Странно, что компайлер на этой строке не матюгнулся...
NEW 08.11.06 10:16
[Недоброжелатель сказал бы, что ошибка -- в днк прокладки:). Шутка:). Ничего личного:).] Пардон. Вычеркнуто после просмотра профиля спрашивавшего
А по сути -- алгоритм выбран странный, далёкий от оптимального. Перефразируя условие задачи -- нужно искать простые числа одно за другим, 1, 2, 3, 5, ... до тех пор, пока счётчик текущего найденного простого числа не сравняется с наперёд заданным значением, и это самое текущее простое число и будет ответом. "Шагать" по ряду натуральных чисел нужно с шагом 2 (чётные числа простыми не бывают), а для проверки на простоту -- делить только на уже найденные простые числа. Вот и вся любовь:).
in Antwort taksos 08.11.06 07:54, Zuletzt geändert 08.11.06 10:20 (barmaglot)
В ответ на:
Пожалуйста, тыкните в ошибку!
Пожалуйста, тыкните в ошибку!
[Недоброжелатель сказал бы, что ошибка -- в днк прокладки:). Шутка:). Ничего личного:).] Пардон. Вычеркнуто после просмотра профиля спрашивавшего
А по сути -- алгоритм выбран странный, далёкий от оптимального. Перефразируя условие задачи -- нужно искать простые числа одно за другим, 1, 2, 3, 5, ... до тех пор, пока счётчик текущего найденного простого числа не сравняется с наперёд заданным значением, и это самое текущее простое число и будет ответом. "Шагать" по ряду натуральных чисел нужно с шагом 2 (чётные числа простыми не бывают), а для проверки на простоту -- делить только на уже найденные простые числа. Вот и вся любовь:).
08.11.06 10:18
in Antwort barmaglot 08.11.06 10:16
Делить здесь абсолютно ничего не надо. Достаточно прибавлять и сравнивать.
NEW 08.11.06 10:28
Я, наверное, дикий. Тему прошу развернуть. В особенности "сравнивать".
in Antwort scorpi_ 08.11.06 10:18
В ответ на:
Достаточно прибавлять и сравнивать.
Достаточно прибавлять и сравнивать.
Я, наверное, дикий. Тему прошу развернуть. В особенности "сравнивать".
NEW 08.11.06 10:29
in Antwort scorpi_ 08.11.06 10:22
Думать здесь надо в первую очередь над алгоритмом.
------
Думать там надо ой как много над чем - над использоваными индентификаторами, над стилем написания, над алгоритмом, над реализацией алгоритма с точки зрения использования памяти, над... тем, об чем писал бармаглот...
Но все эти думания не дадут ответа на заданный вопрос.
------
Думать там надо ой как много над чем - над использоваными индентификаторами, над стилем написания, над алгоритмом, над реализацией алгоритма с точки зрения использования памяти, над... тем, об чем писал бармаглот...
Но все эти думания не дадут ответа на заданный вопрос.
NEW 08.11.06 10:30
in Antwort barmaglot 08.11.06 10:28
NEW 08.11.06 10:36
in Antwort Murr 08.11.06 10:30
О да! Только задолбаться можно, следя за текущим счётчиком-вычёркивателем:).
Кроме того, мальчегу нужны "первые сто простых чисел", а не "простые числа из интервала от одного до ста", а значит априори сходу и не скажешь, до какого числа решетить. ИМХО "мой" алгоритм оптимален с точки зрения затрат на "думание". Ах да, делить конечно можно не на все найденные, а только на те, которые .LE. SQRT (iCurrCounter).
Кроме того, мальчегу нужны "первые сто простых чисел", а не "простые числа из интервала от одного до ста", а значит априори сходу и не скажешь, до какого числа решетить. ИМХО "мой" алгоритм оптимален с точки зрения затрат на "думание". Ах да, делить конечно можно не на все найденные, а только на те, которые .LE. SQRT (iCurrCounter).
NEW 08.11.06 10:40
in Antwort barmaglot 08.11.06 10:36
ИМХО "мой" алгоритм оптимален с точки зрения затрат на "думание".
------
Ты будешь несколько удивлен, но Решето "работает" примерно на три-четыре порядка быстрее... Так что затраты на думание - не существенны...
------
Ты будешь несколько удивлен, но Решето "работает" примерно на три-четыре порядка быстрее... Так что затраты на думание - не существенны...
NEW 08.11.06 10:47
in Antwort Murr 08.11.06 10:40
Хи. Спорю на ящик пива, что для чисел, которые влезаютЪ в интеджер, 4 порядка -- гон. Это первоЕ.
Также прошу представить достоверный метод априорной оценки "длины" решета для наперёд заданного номера простого числа. Это второЕ.
Ну что, "Гиннес" против "Францисканера" :) ?
Также прошу представить достоверный метод априорной оценки "длины" решета для наперёд заданного номера простого числа. Это второЕ.
Ну что, "Гиннес" против "Францисканера" :) ?
NEW 08.11.06 10:58
in Antwort barmaglot 08.11.06 10:47
Спорю
------
Сравни сначала набор операций для обоих случаев.
оценки "длины" решета
------
Верхняя оценка устроит? Для чисел в пределах Int32 - не более 4294967296...
Эээ... зазипованный набор простых чисел в этом диаппазоне весит порядка 70Мб...
------
Сравни сначала набор операций для обоих случаев.
оценки "длины" решета
------
Верхняя оценка устроит? Для чисел в пределах Int32 - не более 4294967296...
Эээ... зазипованный набор простых чисел в этом диаппазоне весит порядка 70Мб...
NEW 08.11.06 10:58
in Antwort barmaglot 08.11.06 10:47, Zuletzt geändert 08.11.06 11:04 (scorpi_)
Также прошу представить достоверный метод априорной оценки "длины" решета для наперёд заданного номера простого числа.
http://de.wikipedia.org/wiki/Primzahlsatz/
http://de.wikipedia.org/wiki/Primzahlsatz/
NEW 08.11.06 10:59
in Antwort barmaglot 08.11.06 10:47
NEW 08.11.06 11:00
Такая -- не устроит. Даю вторую попытку
.
in Antwort Murr 08.11.06 10:58
В ответ на:
Верхняя оценка устроит? Для чисел в пределах Int32 - не более 4294967296...
Верхняя оценка устроит? Для чисел в пределах Int32 - не более 4294967296...
Такая -- не устроит. Даю вторую попытку
.
NEW 08.11.06 11:02
in Antwort barmaglot 08.11.06 11:00
Даю вторую попытку
------
Эээ, нет... теперь твоя очередь оценивать... скажем, количество операций деления для нахождения простого числа с заданным номером...
------
Эээ, нет... теперь твоя очередь оценивать... скажем, количество операций деления для нахождения простого числа с заданным номером...
NEW 08.11.06 12:04
in Antwort Murr 08.11.06 11:02
Ну что ж, из уважения к Вашим сединам сыграю один раз по чужим правилам:).
Я писал о числах, влезающих в интеджер, т. е. до порядка 32 тысяч. В интервале 1..32000 лежит около 2500 простых. Таким образом, если оценивать сверху размером типа, при реализации решета вычеркнуть прийдётся где-то 29500 чисел.
Если, как я предложил, каждое нечётное делить на все простые, которые меньше квадратного корня из него, то делений прийдётся сделать не более чем 16000 умножить на количество простых, которые не превосходят корень из 32000 (это количество -- 41, но на самом деле результат будет меньше, это оценка сверху).
IDL> print, 1.6e4*41.
656000.
Теперь положим, что одно деление жрёт ресурса как 20 сложений, и поделим на заявленные четыре порядка::
IDL> print, 20.*1.6e4*41./1e4
1312.00
Итого:: если бы песня про четыре порядка была правильной, то решето в этом случае потребовало бы меньше, чем 1312 вычёркиваний.
Вердикт:: для типа интеджер четыре порядка -- гон, что и требовалось доказать. Гиннес прошу высылать в Мюнхен. С моей стороны спор окончен.
сыграю один раз по чужим правилам:).Я писал о числах, влезающих в интеджер, т. е. до порядка 32 тысяч. В интервале 1..32000 лежит около 2500 простых. Таким образом, если оценивать сверху размером типа, при реализации решета вычеркнуть прийдётся где-то 29500 чисел.
Если, как я предложил, каждое нечётное делить на все простые, которые меньше квадратного корня из него, то делений прийдётся сделать не более чем 16000 умножить на количество простых, которые не превосходят корень из 32000 (это количество -- 41, но на самом деле результат будет меньше, это оценка сверху).
IDL> print, 1.6e4*41.
656000.
Теперь положим, что одно деление жрёт ресурса как 20 сложений, и поделим на заявленные четыре порядка::
IDL> print, 20.*1.6e4*41./1e4
1312.00
Итого:: если бы песня про четыре порядка была правильной, то решето в этом случае потребовало бы меньше, чем 1312 вычёркиваний.
Вердикт:: для типа интеджер четыре порядка -- гон, что и требовалось доказать. Гиннес прошу высылать в Мюнхен
. С моей стороны спор окончен.