Форум на Исходниках.RU

Простые числа

husp — Sun, 04 Dec 2011 13:52:35 +0000

husp: Реализация решета Эратосфена генерации простых чисел, алгоритм на пескале, качайте, смотрите стр. 389
http://bnivanov.ru/book/Discrete_mathematics_BN_Ivanov.pdf

Простые числа

EXcell — Fri, 22 Apr 2005 15:59:53 +0000

EXcell: что вы имеете в виду под вероятностными алгоритмами? Не модифицированный ли алгоритм поиска с помощью Малой Теоремы Ферма или алгоритм Рабина?

Простые числа

experimenter — Sun, 02 Jan 2005 15:31:19 +0000

experimenter: не удержался. :D
эй,Прохожий,проходи, эх... :D :D :D

Простые числа

Прохожий — Sun, 02 Jan 2005 07:47:42 +0000

Прохожий: ПервыйНах
Дааааа за 2 года на этом крутом сайте ни кто не исправил не доведёное до конца
док Эвклида о бесконечности простых
Итак Fix:
1.пусть мы нашли все простые P[i]
2. Перемножим Их получим новое число YesBabbyBig=Произведение(i от 1 до n ) Итое проестое число
3. увеличим число на одие OneMore=YesBabbyBig+1
4. очевидно(ха ха) чё в разложении OneMore:
а) будет присутствовать новое простое след пришли к противоречию след Простых много

Для тех кому не очевидно 4.а :
Пусть Докажут Обратное :)

Простые числа

AVA12 — Thu, 30 Dec 2004 18:17:10 +0000

AVA12: 2 vadim2002:

Цитата

все меньшие простые числа включая данное число перемножим и прибавим 1. Полученное число простое - ;)

Неверно!

2*3*5*7*11*13 + 1 = 30031 = 59*509
2*3*5*7*11*13*17 + 1 = 510511 = 19*97*277
2*3*5*7*11*13*17*19 + 1 = 9699691 = 347*27953
2*3*5*7*11*13*17*19*23 + 1 = 223092871 = 317*703763

P. S. Упоминавшаяся статья называется "Primes in P".

Простые числа

Guest — Thu, 30 Dec 2004 13:18:19 +0000

Guest:

Цитата Шут @ 17.02.04, 12:17

очень простой статистике распределения

интересно какой?

Простые числа

Guest — Thu, 30 Dec 2004 12:16:29 +0000

Guest: Уважаемый Alexvp вышлете мне пожалуйста статью индийских коллег на адрес - alexys_@mail.ru - зараннее благодарен!

Простые числа

Шут — Tue, 17 Feb 2004 09:17:59 +0000

Шут: Ваабще простые числа подчиняются очень простой статистике распределения. И самое забавное что это довольно просто... всё упирается в мощь компа... вероятностный метод немного излишен - вероятность не определят само число...К слову - по формуле Шредингера я тоже могу пройти сквозь стенку, благодаря туннельному эффекту...

Простые числа

esperanto — Tue, 24 Dec 2002 08:43:16 +0000

esperanto:

Цитата Demo_S, 24.12.02, 01:35:17

2Netta статейку давай:) или тут, или мылом:)
2experimenter да, действительно.. можно конечно еще поищвращаться над принципом выборки этих чисел... но думаю не сильно поможет:)
кстати, если таки эти индийцы придумали действительно быстрый алг-м проверки числа на простоту, то ведь все фирмы, выпускающие криптующие продукты (PGP тот же) должны поднять вой, а тихо...

вы похоже не доконца суть понимаете

то что найдена проверка чисел на простоту еще не значит что мы можем быстро расскладывать на простые множители !!!

поэтому вой поднимать незачем

да и до этого были быстрые вероятностные алгоритмы

вот если бы это задача была НП полной то да было бы круто а так ((

Простые числа

Demo_S — Mon, 23 Dec 2002 22:35:17 +0000

Demo_S: 2Netta статейку давай:) или тут, или мылом:)
2experimenter да, действительно.. можно конечно еще поищвращаться над принципом выборки этих чисел... но думаю не сильно поможет:)
кстати, если таки эти индийцы придумали действительно быстрый алг-м проверки числа на простоту, то ведь все фирмы, выпускающие криптующие продукты (PGP тот же) должны поднять вой, а тихо...

Простые числа

volatile — Mon, 23 Dec 2002 16:58:01 +0000

volatile: Предположим:
a₀=2
a_n+1=П_i=1,n(a_i)+1//произведение всех предыдущих+1

имеем:
a₀=2
a₁=2+1=3
a₂=2*3+1=7 !!! (пропустили простое число 5)
a₃=2*3*7+1=43
a₄=2*3*7*43+1=1807=13*139

итак - уже пятое число получили составное.

Простые числа

Netta — Mon, 23 Dec 2002 16:53:09 +0000

Netta: Если нет, то у меня на русском статейка эта уже есть - если будет кому-то интересно - я ее здесь опубликую.

Простые числа

Netta — Mon, 23 Dec 2002 16:47:25 +0000

Netta: Этот индийский алгоритм кто-нибуть все-таки получил?

Простые числа

experimenter — Mon, 23 Dec 2002 16:21:05 +0000

experimenter: просто надо перемножать все первые (а это крайне легко сломать), т.к.
1*2*3*5 + 1 = 31,но

3*5 + 1 = 16
Я думаю поэтому.

Простые числа

Demo_S — Mon, 23 Dec 2002 15:20:13 +0000

Demo_S: Но откуда он знает, какие именно из первіх 1000 простых чисел мы перемножили?

Простые числа

esperanto — Sun, 22 Dec 2002 08:07:09 +0000

esperanto: проблема в том что если мы таким образом будем генерировать простые числа то
предположим мы таким образом сгенерировали два числа перемножили и послали проьивнику
наша цель чтобы он не мог их разложить на множители но если их получать по вашей системе то он разложит без труда поэтому
плохо

Простые числа

Demo_S — Sat, 21 Dec 2002 14:17:23 +0000

Demo_S: ты хотел сказать четное:)
при перемножении простых чисел будет как раз четное, тк 2 - это тоже простое:)
перемножь 2*3*5*7*11*13*17*19*... -рез-т будет четным:)

Простые числа

Muller — Fri, 20 Dec 2002 12:17:13 +0000

Muller: Почти 100\%, что полученное число не проистое, оно ПАРНОЕ
так как при перемножении прстых чисел будет число непарное, то на 1 большее - парное!!!

Простые числа

experimenter — Wed, 18 Dec 2002 16:02:28 +0000

experimenter: а чего бы вот таким макаром не получать простые числа? ну, чуть модифицировать там алгоритмик? Наверное, я что-то революционное придумал!
;D ;D ;D
Мне тоже кажется, что самое классное - это вероятностные алгритмы - их так просто не расскажешь. Они не сложные, но типа хитрые, т.к. идет работы с большими числами.

Простые числа

vadim2002 — Wed, 18 Dec 2002 12:09:20 +0000

vadim2002: Четкое доказательство что данное число простое - неизвестно (хотя насегодня это не значит, что его нет) В алгоритме RSA стоит задача пролучения ОЧЕНЬ ОЧЕНЬ больших простых чисел, это делается вероятностными алгоритмами, они случайно генерируют числа с очень большой вероятностью, что они простые. А точная проверка числа на простое - это перебор делением на все известные простые числа до квадр. корня от данного. В заключение теорема о том, что не существует максимального простого числа: предположим что найдено максимальное простое число все меньшие простые числа включая данное число перемножим и прибавим 1. Полученное число простое - ;)

Простые числа

esperanto — Mon, 16 Dec 2002 09:14:14 +0000

esperanto:

Если не хватит размерности, сделай динамический массив. :)))
[/quote]

я конечно извиняюсь но решето это детский сад ибо алгоритм экспоненциальный и используют только вероятностные алгоритмы

Простые числа

Starks — Mon, 16 Dec 2002 08:45:47 +0000

Starks: Алгоритм "Решето Эратосфена". Вот такой вариант:

uses crt;
const n=100;
var a:array[1..n] of boolean;
i,j:word;
begin
clrscr;

for i:=1 to n do
a[i]:=true;

for i:=2 to n do
if a[i] then begin
j:=2*i;
while j <= n do begin
a[j]:=false; j:=j+i
end; end;

for i:=1 to n do
if a[i] then write(i:5); readkey;
end.

Если не хватит размерности, сделай динамический массив. :)))

Простые числа

esperanto — Wed, 11 Dec 2002 15:13:21 +0000

esperanto: a^(p-1)=1 mod p если р простое поэтому если число не удовлетворяет уравнению то оно не простое
проблема в том что существуют не простые числе которые тоже удовлетворяют уравнению

для этого аллгоритм надо улучшить как правмло работаютс вероятностными алгоритмами

Простые числа

Muller — Wed, 11 Dec 2002 12:40:25 +0000

Muller: Можете прислать мне статьи и методы решений на muller@front.ru, plz
Перебор не подходит, так как это долго, я сам пробовал токой вариант.
Про малую теорему ферма я слышал, но непонял, и был бы благодарен за объяснение по-подробней

Простые числа

esperanto — Sun, 24 Nov 2002 18:17:20 +0000

esperanto: есть хорошие вероятностные алгоритмы которые с вероятностью более 0.5 отвечают является ли число простым.
основываются на малой теореме ферма китайской об остатках
и тп

Простые числа

Rumata — Sun, 24 Nov 2002 01:48:35 +0000

Rumata:

Цитата Muller, 22.11.02, 12:44:02

Как доказать, что число простое?
Как найти все простые числа из диапазона(например 1..428000000)?

сложно это ибо нет формулы и нет системы в появлении простых чисел

есть простой алгоритм "решето Эратосфена". он отсеивает все числа кроме простых.

или можно так

var R, I: Integer; begin Writeln('Программа определения простого числа'); Writeln; Write('Введи число '); Readln(R); if (R = 1) or (R = 2) then Writeln(R, ' тоже простое число') else if (R mod 2 = 0) then Writeln('Это число четное') else begin I := 3; while R mod I <> 0 do I := I + 2; if R <= I then Writeln('Это число простое') else Writeln('Это число непростое'); end; end.

Простые числа

shadeofgray — Sat, 23 Nov 2002 12:11:50 +0000

shadeofgray: и мне статью плиз, пришли: shadeofgray@yandex.ru

Простые числа

Demo_S — Fri, 22 Nov 2002 22:27:06 +0000

Demo_S: вообще есть куча алгоритмов определения, простое число или нет... и вовсе не перебором:) (ну почти, что-то от перебора там коенчно остается). надо найти,я курсак на эту тему писал...
2Alexvp
статейку давай.
я про это слышал. а самой статьи так и не видел....
очень даже надо:)п
присылай на Demo_s{}ua.fm :)(чтобы тебе лишний раз в профайл не лезть:)

Простые числа

Alexvp — Fri, 22 Nov 2002 16:43:10 +0000

Alexvp: Если интересно то могу статейку одну выслать там индийские кулибины алгоритм наваяли там его оисание довольно подробное (правда на английском) тока собщи куда... (воетолько не уверен что до понедельника доберусь до рабочего компа )

Простые числа

shadeofgray — Fri, 22 Nov 2002 12:25:05 +0000

shadeofgray: можно в несколько раз ускорить перебор, если запоминать предыдущие найденные простые числа и делить не на все числа от 2 до sqrt(N), а только на простые.

Простые числа

PropellerMan — Fri, 22 Nov 2002 10:13:19 +0000

PropellerMan: Не, перебор - это плохо. Из первых десяти миллионов чисел - 650000 простых вышло. Да и медленно он все делает.

Простые числа

PropellerMan — Fri, 22 Nov 2002 09:57:08 +0000

PropellerMan: Если искать простым перебором, то можно облегчить себе жизнь и для данного числа искать его множители от 2 до корня из данного числа. Например, ищем разложение числа 100. Для этого надо пройти все числа от 2 до 10. В свое время кульные математики нашли офигенно большие простые числа (да и ща ищут), но помоему доказательство их простоты - это не перебор.

Простые числа

Muller — Fri, 22 Nov 2002 09:44:02 +0000

Muller: Как доказать, что число простое?
Как найти все простые числа из диапазона(например 1..428000000)?