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

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

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

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

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

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

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

Сообщение отредактировано: Demo_S - 01.02.04, 15:55

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

Сообщение отредактировано: shadeofgray - 23.11.02, 12:12

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

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

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

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

или можно так

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

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

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

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

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

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


    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.

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

Сообщение отредактировано: Starks - 16.12.02, 08:50

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

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

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

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

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

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

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

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

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

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

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

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

Предположим:
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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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".

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


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

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

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

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