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

Как доказать, что число простое?
Как найти все простые числа из диапазона(например 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
Мне тоже кажется, что самое классное - это вероятностные алгритмы - их так просто не расскажешь. Они не сложные, но типа хитрые, т.к. идет работы с большими числами.