Алгоритм поиска ближайшего простого числа

← →
r@bbit (2006-07-23 17:07) [0]

Народ, помогите плиз! Требуется найти ближайшее простое число к заданному N (WORD), перебрать числа в прямом и обратном от N порядке не проблема, но как быстро и правильно определить простое ли оно? Вопрос туповат конечно, но раньше такого не делал, изобретать изобретённое неохота - лаба того не стоит. Нужен принцип определения простое ли число. Попроще принцип, если можно :) Заранее благодарен.

← →
Palladin © (2006-07-23 17:23) [1]

попроще? без проблемм :)

Function IsSimple(n:Integer):Boolean;
Var
i:Integer;
Begin
Result:=False;
For i:=2 to n-1 Do If (n mod i)=0 Then Exit;
Result:=True;
End;

← →
Palladin © (2006-07-23 17:25) [2]

или еще лучше
For i:=2 to (n div 2)

← →
r@bbit (2006-07-23 18:52) [3]

>Palladin
сенькс! вообще я предполагал, что делений будет поменьше... а так получается цикл до N div 2. хммм... то есть если число скажем 1000 то делений будет около 500...

← →
Ketmar © (2006-07-23 19:03) [4]

>r@bbit (23.07.06 18:52) [3]
для тысячи будет ровно одно. %-)

← →
Desdechado © (2006-07-23 19:35) [5]

Ketmar © (23.07.06 19:03) [4]
Нет. Ему ж найти ближайшее простое (видимо, в обе стороны), а не выяснить, простое ли данное.

← →
Palladin © (2006-07-23 19:52) [6]

> Desdechado © (23.07.06 19:35) [5]

В смысле нет? для 1000 будет именно одно... только на 2. А вот для 1009 будет аж 504.

← →
Desdechado © (2006-07-23 20:04) [7]

> для 1000 будет именно одно..
Это для выяснения, что 1000 - не простое. А для поиска ближайшего простого сколько итераций?

← →
Palladin © (2006-07-23 20:22) [8]

> Desdechado © (23.07.06 20:04) [7]

в [3] имелось в виду именно проверка

← →
Vendict © (2006-07-23 20:25) [9]

r@bbit (23.07.06 17:07) [0]
я думаю стоит просто проверить на простоту числа +/-20 к примеру и найти ближайшее.
есть вероятностные методы с меньшей сложностью, чем деление на всё что меньше:

http://algolist.manual.ru/maths/teornum/
http://algolist.manual.ru/maths/teornum/rabmil.php
и генерация http://algolist.manual.ru/maths/teornum/gene_prime.php

← →
Lamer@fools.ua © (2006-07-23 21:43) [10]

>>Palladin © (23.07.06 17:25) [2]

>или еще лучше
>For i:=2 to (n div 2)

Лучше, IMHO, всё-таки хотя бы так:
function IsPrime(n: Cardinal): Boolean; var i, maxI: Cardinal; begin Result := False; if not Odd(n) and (n > 2) then Exit; maxI := Trunc(Sqrt(n)); i := 3; while i <= maxI do begin if n mod i = 0 then Exit; Inc(i, 2); end; Result:=True; end;

← →
default © (2006-07-23 22:19) [11]

WORD это 65536 значений
на каждое значение - единственное ближайшее простое число(если так вышло, что для какого-то числа два ближайших простых, выбрать по какому-либо правилу - одно)
я к тому, что можно один раз посчитать для всех значений простые числа и потом использовать готовый результат, если памяти не жалко и есть её
есть ещё идея - посчитай для всех значений простых чисел и внимательно присмотрись
очень вероятно, что можно увидеть какие-либо закономерности нахождения ближайших простых чисел для первых 65536 чисел, на основе замеченного вполне возможно удастся очень даже заметно сократить перебор это если без хранения всего в памяти обходиться

← →
default © (2006-07-23 22:36) [12]

+[11]
"посчитай для всех значений простых чисел "-->посчитай для всех значений ближайшие простые числа
"и внимательно присмотрись"
тут я малость погорячился, ибо 65536 чисел для человека - необозримая совокупность
самое очевидное, можно найти максимальное расстояние на котором может находиться от заданного числа его ближайшее простое число, чтобы сократить перебор
можно проверить другие эвристики(догадки) относительно возможных закнономерностей(в цикле конечно, взглядом закономерность тут не подметить)
это если конечно - скорость критична, а память использовать нельзя по каким-либо причинам

← →
jack128 © (2006-07-23 22:47) [13]

default © (23.07.06 22:36) [12]
а память использовать нельзя по каким-либо причинам
сложно представить себе ситуацию при которой было бы жалко 13 кило единовременно выделить..

← →
Думкин © (2006-07-24 06:34) [14]

Корень из 65536 = 256. Число простых чисел до 256 - весьма мало. Порядка 46 штук. И находятся весьма быстро с тем же решетом. После этого найти ближайшее к любому вне этого ряда до 256 - дело техники.

← →
pasha_golub © (2006-07-24 12:01) [15]

На algolist.manual.ru есть несколько алгоритмов. Хотя бля лабы действительно многовато.

← →
default © (2006-07-24 12:03) [16]

pasha_golub © (24.07.06 12:01) [15]
а вот материться не надо:)

← →
TUser © (2006-07-24 15:52) [17]

Не претендуя на откровение положу-ка я тут наивный код. На диапазоне 2..high(word) подготовка времени не занимает вообще, а поиск - будет хорошо работать в любом диапазоне.

program n; {$apptype console} uses SysUtils; var Ar: array of word; Cn: integer; procedure Add (N: word); begin inc (Cn); if Cn > length (Ar) then SetLength (Ar, Cn * 2); Ar[Cn - 1] := N; end; function IsSimple (N: word): boolean; var i: integer; q: double; begin result := true; q := sqrt (N); for i := 0 to Cn - 1 do if Ar[i] > q then exit else if (N mod Ar[i]) = 0 then begin result := false; exit; end; end; function Nearest (N: word; var R: word): boolean; var l, h, m: integer; begin l := 0; h := Cn - 1; if L >= h then begin result := false; exit; end; result := true; repeat m := (l + h) shr 1; if Ar[m] < N then l := m + 1 else h := m - 1; until l > h; R := Ar[m]; if m > 0 then if abs (R - N) > abs (Ar[m-1] - N) then R := Ar[m - 1]; if m < Cn then if abs (R - N) > abs (Ar[m+1] - N) then R := Ar[m + 1]; end; var i, j: word; s: string; begin Cn := 0; writeln ("Preparing"); Add (2); for i := 3 to high (word) do if IsSimple (i) then Add (i); writeln; repeat write ("Enter a number: "); readln (s); try i := StrToInt (s); if Nearest (i, j) then writeln ("The nearest simple number for ", i, " is ", j) else writeln ("The nearest number for ", i, " was not found"); except writeln ("error"); end; until false; end.

← →
Vendict © (2006-07-24 21:34) [18]

Думкин © (24.07.06 6:34) [14]
Корень из 65536 = 256. Число простых чисел до 256 - весьма мало. Порядка 46 штук. И находятся весьма быстро с тем же решетом. После этого найти ближайшее к любому вне этого ряда до 256 - дело техники.
А если ближайшее - сильное простое ? (т.е. (n-1)\2=0 если n простое) то придтся периберать до (n div 2) или как-то ещё изворачиваться. не проще проверить одним из алгоритмов числа +-20 ?

← →
Думкин © (2006-07-25 05:52) [19]

> Vendict © (24.07.06 21:34) [18]

? ???? strong simple? - eto est bred?

← →
Думкин © (2006-07-25 06:13) [20]

> Vendict © (24.07.06 21:34) [18]

Извиняюсь за свой английский в предыддущем посте - комп переклинило и не хотел переключаться на русское. Перегрузился.
Так вот, если не затруднит, то проясните мне следующее:
1. Что есть сильное простое?
2. Причем тут изворачиваться?
3. Почему ваш алгоритм быстрее?

← →
Vendict © (2006-07-25 19:36) [21]

Думкин © (25.07.06 6:13) [20]
1. Что есть сильное простое?
2. Причем тут изворачиваться?
3. Почему ваш алгоритм быстрее?

1. p - сильное простое, если (p-1) имеет большой простой делитель.
2. придётся или искать числа до р/2 или проверять при методе пробного деления, простое ли число осталось.
3. Алгоритм генерации простых чисел около O(n div 2) тот алгоритм, который проверяет число на простоту порядка O(m), где m - количество проверок, такое что 0.5^m достаточно близко к 0лю.

← →
Vendict © (2006-07-25 19:38) [22]

И я думаю лаба и нацелена на использование вероятностных алгоритмов проверки на простоту.
И вдруг у нас не Word а LongWord, то скорость будет заметна.

← →
StriderMan © (2006-07-25 19:38) [23]

> Vendict © (25.07.06 19:36) [21]
> 1. p - сильное простое, если (p-1) имеет большой простой
> делитель

насколько большой? что значит большой?

← →
SergP. (2006-07-25 19:59) [24]

> Palladin © (23.07.06 17:25) [2]
> или еще лучше
> For i:=2 to (n div 2)

Это еще не самый лучший вариант...

StriderMan © (25.07.06 19:38) [23]
насколько большой? что значит большой?
"сильное простое" данный термин используется в криптографии как я написал "p - сильное простое, если (p-1) имеет большой простой делитель." логично, имеется ввиду больше корня из p.

> Vendict ©

Значит вы просто не прочитали то, что предложил я. Ну и безусловно - не вникли. А вы попробуйте и заберите свои слова назад. У вас получится, если постараетесь. Это еще Роллинги утверждали.

> Vendict © (25.07.06 20:18) [25]

Раз оно имеет такой большой делитель, то по логике оно должно иметь и меньший. Дойдя до оного и поймем - что число не простой. В чем загвоздка?

318-225-800

Думкин © (26.07.06 05:42) [27]

> Дойдя до оного и поймем - что число не простоe.

Конечно, не простое. Если p - большое простое, то p-1 - не только не простое, оно четное. А "сильное" простое число ищут, чтобы затруднить попытки разложения на множители некоторым вероятностным алгоритмом, который как раз плохо работает для таких сильных простых. Подробности я не знаю, но в книжках об этом пишут.

> palva © (26.07.06 11:04) [31]

То что оно четное - это ясно. :)
Но каким боком это относится к написаному мной - лично я так и не увидел. :)

> palva © (26.07.06 11:17) [33]

Вы поняли правильно. Но я принял данное выше определение "сильного простого". А вот каким боком оно усложнит предложенный мной метод - не увидел. После нахождения массива первых простых чисел, каждая проверка числа на простоту потребует в худшем варанте порядка n^0.5/ln(n^0.5) нахождений остатков, что значительно лучше чем (n div 2).

Ведь тепатировать можно, что угодно в том числе и такое:

> И я думаю лаба и нацелена на использование вероятностных
> алгоритмов проверки на простоту.

А к чему?

К тому же для нахождения этих чисел до 256 достаточно провести расчеты с 2,3,5,7,11,13. И даже в случае с LongWord все не так грустно. Массив будет порядка 6000 элементов.

Алгоритм поиска ближайшего простого числа Найти похожие ветки