Вход на сайт
Поиск простого числа
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 10:16
[Недоброжелатель сказал бы, что ошибка -- в днк прокладки:). Шутка:). Ничего личного:).] Пардон. Вычеркнуто после просмотра профиля спрашивавшего
А по сути -- алгоритм выбран странный, далёкий от оптимального. Перефразируя условие задачи -- нужно искать простые числа одно за другим, 1, 2, 3, 5, ... до тех пор, пока счётчик текущего найденного простого числа не сравняется с наперёд заданным значением, и это самое текущее простое число и будет ответом. "Шагать" по ряду натуральных чисел нужно с шагом 2 (чётные числа простыми не бывают), а для проверки на простоту -- делить только на уже найденные простые числа. Вот и вся любовь:).
В ответ на:
Пожалуйста, тыкните в ошибку!
Пожалуйста, тыкните в ошибку!
[Недоброжелатель сказал бы, что ошибка -- в днк прокладки:). Шутка:). Ничего личного:).] Пардон. Вычеркнуто после просмотра профиля спрашивавшего
А по сути -- алгоритм выбран странный, далёкий от оптимального. Перефразируя условие задачи -- нужно искать простые числа одно за другим, 1, 2, 3, 5, ... до тех пор, пока счётчик текущего найденного простого числа не сравняется с наперёд заданным значением, и это самое текущее простое число и будет ответом. "Шагать" по ряду натуральных чисел нужно с шагом 2 (чётные числа простыми не бывают), а для проверки на простоту -- делить только на уже найденные простые числа. Вот и вся любовь:).
NEW 08.11.06 10:29
в ответ scorpi_ 08.11.06 10:22
Думать здесь надо в первую очередь над алгоритмом.
------
Думать там надо ой как много над чем - над использоваными индентификаторами, над стилем написания, над алгоритмом, над реализацией алгоритма с точки зрения использования памяти, над... тем, об чем писал бармаглот...
Но все эти думания не дадут ответа на заданный вопрос.
------
Думать там надо ой как много над чем - над использоваными индентификаторами, над стилем написания, над алгоритмом, над реализацией алгоритма с точки зрения использования памяти, над... тем, об чем писал бармаглот...
Но все эти думания не дадут ответа на заданный вопрос.
08.11.06 10:36
в ответ Murr 08.11.06 10:30
О да! Только задолбаться можно, следя за текущим счётчиком-вычёркивателем:).
Кроме того, мальчегу нужны "первые сто простых чисел", а не "простые числа из интервала от одного до ста", а значит априори сходу и не скажешь, до какого числа решетить. ИМХО "мой" алгоритм оптимален с точки зрения затрат на "думание". Ах да, делить конечно можно не на все найденные, а только на те, которые .LE. SQRT (iCurrCounter).
Кроме того, мальчегу нужны "первые сто простых чисел", а не "простые числа из интервала от одного до ста", а значит априори сходу и не скажешь, до какого числа решетить. ИМХО "мой" алгоритм оптимален с точки зрения затрат на "думание". Ах да, делить конечно можно не на все найденные, а только на те, которые .LE. SQRT (iCurrCounter).
NEW 08.11.06 10:47
в ответ Murr 08.11.06 10:40
Хи. Спорю на ящик пива, что для чисел, которые влезаютЪ в интеджер, 4 порядка -- гон. Это первоЕ.
Также прошу представить достоверный метод априорной оценки "длины" решета для наперёд заданного номера простого числа. Это второЕ.
Ну что, "Гиннес" против "Францисканера" :) ?
Также прошу представить достоверный метод априорной оценки "длины" решета для наперёд заданного номера простого числа. Это второЕ.
Ну что, "Гиннес" против "Францисканера" :) ?
NEW 08.11.06 10:58
Также прошу представить достоверный метод априорной оценки "длины" решета для наперёд заданного номера простого числа.
http://de.wikipedia.org/wiki/Primzahlsatz/
http://de.wikipedia.org/wiki/Primzahlsatz/
NEW 08.11.06 12:04
в ответ 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 вычёркиваний.
Вердикт:: для типа интеджер четыре порядка -- гон, что и требовалось доказать. Гиннес прошу высылать в Мюнхен
. С моей стороны спор окончен.