| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Оцените код для нахождения простых чисел |
| Автор: Mura-vey 4.1.2003, 06:24 |
| program Ishem_prostie_chisla_v_sotne; uses crt; var a,b : array [1..100] of byte; p : byte; i,n,z : byte; label l,l2; begin ClrScr; a[1]:=3; b[1]:=3; i:=3; n:=0; l: p:=0; for z := 1 to n do begin b[z]:=b[z]-1; if b[z] = 0 then begin b[z]:=a[z]; p := 1; {goto l2;} end; end; if p<>1 then begin n:=n+1; a[n]:=i; b[n]:=i; write(a[n],' '); end; l2: i:=i + 2; {write(i,' ');} if i<=100 then goto l; {for i := 1 to 24 do begin write(a[i],' '); end;} write(n); end. Я долго коптил, и нашёл закономерность "размножения" простых чисел. (кто не верит пусть компилит!!!!) Я прошу помощи перевода етого кода на асм, при этом надо сделать возможность бесконечного увеличения массива. заранее сенкс |
| Автор: podval 5.1.2003, 05:29 |
| И чем конкретно этот метод новый? |
| Автор: Kefir 10.1.2003, 07:29 |
| Я вообще особо не рублю на Дельфи/Паскале, но... вообще на кой чёрт тебе искать эти числа? ведь можно просто брать число, проверять простое оно или нет, потом, если оно простое кидать его в файл или куда надо. на С++ что то в роде: int num_to_check = 1000; for(int a = 0; a<num_to_check; a++) if(Prostoje4islo(a)==TRUE) printf("%i\n", a); Ф-ция Prostoje4islo проверяет простое ли число и, если да, то printf выводит это число на экран. Не верю, что на Паскали/Дельфи так нельзя сделать. |
| Автор: Vit 10.1.2003, 08:14 |
| 2 Kefir - можно конечно, но проблема с простыми числами остаётся весьма острой, код автора тоже не поможет. Например видоизменим задачу - надо найти все простые числа в интервале от 10^20 до 10^22... Желательно за разумный интервал времени... |
| Автор: Dapo 10.1.2003, 17:21 |
| "Я долго коптил, и нашёл закономерность "размножения" простых чисел. " Смелое утверждение :-). Если ты действительно сформулировал закон распределения простых чисел, тогда тебе нужно премию, как минимум, Филдса выдать. Кстати, кажется на Vingrade в каком-то разделе форума кто-то статью выдал, что какие-то ученые составили алгоритм получения простого числа, но чего-то я больше нигде подобной информации не читал. Для тех кто не в курсе (мало ли как бывает) простые числа - число которые деляться только на 1 и на себя (1,2,3,5,7,11,13,17 и т.д. (только вот как так? :-) ) ). |
| Автор: Kefir 10.1.2003, 18:36 |
| 2 Vit: Это примерно 99 в 20й итераций... нда... хорошего времени не получается, но быстродействие компьютеров постоянно растёт, так что очень возможно, что вскоре и такой способ подойдёт. Вообще я не имел в виду таких астрономических чисел, просто при довольно нечасто надо находить все простые в этом интервале. 2 Dapo: Может ты это имел в виду: http://www.cse.iitk.ac.in/primality.pdf ? Это алгоритм дающий 100% уверенность в простоте числа (или же в том что оно не простое). |
| Автор: maxim1000 11.1.2003, 01:05 |
| Дело в том, что над этой проблемой "покоптили" еще в древности. В результате появился метод с названием "решето Эратосфена", который довольно часто изучается в школе... если интересно - сходите, например, на www.nature.ru и наберите в поиске "решето Эратосфена" |
| Автор: Kefir 11.1.2003, 01:21 |
| 2 maxim1000: Решето - это конечно хорошо, но и ты тоже не поленись, зайди по ссылке в моём предидущем мсг. Тоже довольно интересно. |
| Автор: Vit 11.1.2003, 02:46 |
| Тема перемещена в раздел алгоритмов |
| Автор: Paradox 27.2.2003, 15:43 |
| А как же Кнут с его алгоритмами..... |
| Автор: BlackWolf 2.4.2003, 21:11 |
| Поиск простых чисел практически нужен например в криптоанализе системы шифрования с открытым ключом (например RSA). По крайней мере очень сильно убыстрит его. |
| Автор: neutrino 10.4.2003, 14:54 |
| Ну вот, народ, ловите. Кто тут говорил, что статью хотел: http://www.cse.iitk.ac.in/news/primality.pdf |
| Автор: df_3 27.5.2003, 08:58 |
| Сделай exe и дизасемблируй его ))) Вот тебе и код в АСМ |
| Автор: df_3 27.5.2003, 08:59 |
| а так нормально! но лучше в динамической памяти Так как на большие массивы места не хватит) |
| Автор: Гость_Victor 28.9.2004, 11:18 |
| Выведена формула получения простых чисел http://www.laplas.narod.ru/moiform.htm пункт №4 где k целое число от 1 до бесконечности. Выражение в скобках ограниченных снизу обозначает целую часть дроби k/6, либо само значение этой дроби если k кратно 6, ну а функция n=[(k-1)mod(6)] и n=[(k)mod(6)] вам я надеюсь знакома - сравнимость чисел n и k-1, k по модулю 6. Эта формула даёт все простые числа по порядку начиная с 5. Так же по этой формуле получаются составные числа. Общая доля отсева равна 11/15=0.73333(3). |
| Автор: cardinal 28.9.2004, 13:05 | ||
Или посмотритет тут: http://forum.vingrad.ru/index.php?showtopic=30076 |
| Автор: Y-Vladimir 28.9.2004, 13:07 | ||||
Может я не вьехал во что-то, но вот фразу:
я не совсем понял... А чем эта формула отличается по смыслу от известной 2^n - 1, там вроде тоже простые получаются числа и составные иногда проскакивают...
Есть формула асимптотического распределения простых чисел: p(x) = x/ln x показывающая, сколько простых числе содержится на интервале 1..x. |
| Автор: LuckLess 29.9.2004, 17:21 | ||
непойму , какой смысл в формуле , если можно легко сделать общую долю отсева 0.5 проверяя только нечетные числа.. |
| Автор: III.nfo 19.10.2004, 08:19 |
| Для программной проверки на простоту: // language C# int IsProstoe = ...; // Объявляется переменная с числом. // Проверяется делимость на два. % - деление по модулю. if ((IsProstoe % 2) == 0) { MessageBox.Show ("Не простое!"); } for (i = 3; i != (IsProstoe / 2); i+2) { if ((IsProstoe % i) == 0) { MessageBox.Show ("Не простое!"); } } Суть действия: Сначала для быстроты исполнения проверяется на 2. -50% случайных чисел. Затем идёт перебор для нечётных чисел, больших еденицы и меньших половины числа. По-моему, хоть это и не самый, возможно, быстрый код, но он надёжен и прост в реализации, а затем будущим программерам в него будет легко въехать (начиная от таких, как я, 10-классников). Для поиска вводится цикл, в который это помещается. int MaxProstoe = ...; for (int IsProstoe = 1; IsProstoe != MaxProstoe) {...} |
| Автор: Baib 23.10.2004, 20:11 |
| Во-первых, 1 - не простое... Люди не в курсе где можно найти Кнута в электронном виде? А то вы тут его вспоминали... |
| Автор: EKoshelev 16.11.2004, 12:36 |
| У меня книжка на винте валяется по криптоанализу. Там вроде метод есть, с помощью которого можно найти простое число нужного порядка. Только там много слов непонятных и не разобрался как это делается. А по Эратосфену я сам писал. Нашёл все в пределах 80 000 000 000. |
| Автор: EKoshelev 23.11.2004, 10:10 |
| У меня даже прога валяется где-то (и работает в пределах 20 минут на 400 МГц). Если интересно... |
| Автор: Guest 23.11.2004, 10:37 |
| |
| Автор: Гость_Sanek 14.4.2005, 16:27 |
Помоему этот попроще будет))... И ищет не только в сотне. И в 1000000 нейдёт... всё простые, только немного подождать придётся  . Зацените.Program gen; uses crt; var n,k,t,sum,m: longint; begin clrscr; textcolor (2); sum:=0; Read (m); for n:=1 to m do begin t:=1; k:=2; while (k<n-1) and (t<>0) do begin t:=n mod k; k:=k+1; end; if t=0 then write ('') else begin Write (' ',n); inc(sum); end; end; writeLn; writeLn (sum); readkey; end. |
| Автор: 0d5a 30.5.2007, 09:06 | ||
| Кнута здесь посмотреть можно http://www.poiskknig.ru/ Добавлено через 2 минуты и 16 секунд А можно так, хотя почти тоже самое Delphi:
|
| Автор: Artemios 30.5.2007, 15:49 | ||||
Можно, и я свою лепту внесу  язык Haskell. Потенциально бесконечная последовательность простых чисел, используется классическое определение простого числа:
Пример взят http://ru.wikibooks.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D1%87%D0%B8%D1%81%D0%B5%D0%BB_%D0%B8_%D1%8F%D0%B7%D1%8B%D0%BA_Haskell. Потенциально бесконечная последовательность простых чисел, используется решето Эратосфена:
пример мой. |
| Автор: dimoid_12 15.6.2007, 01:04 |
| sorry |
| Автор: SoWa 7.7.2007, 19:52 |
| Еще есть полином Мятисевича (как раз тут и обсуждался) только ничего разумного по нему найти не могу. Кто найдет- дам плюсик ) |
| Автор: Julius 6.8.2007, 10:36 |
есть еще косвенные методы) сейчас к примеру иногда используется малая теорема ферма за исключением чисел кармайкла. Только для этого нужны компьютеры побольше  |
| Автор: ProgBeat 7.8.2007, 00:22 | ||
этот алгоритм ничем не отличается от самого тривиального алгоритма b[z] = (a[z]-((i-a[z])/2%a[z]))%a[z] // при проверке на равенство нулю b[z] = a[z]-((i-a[z])/2%a[z]) // после проверки (a[z]-((i-a[z])/2%a[z]))%a[z] = 0 <=> i-a[z]=0(mod 2*a[z]) <=> cуществует такое k (1+2*k - нечётное, чётные можно не проверять), при котором i=a[z]*(1+2*k) // % - остаток от деления если заменить if b[z] = 0 then begin на if i Mod a[z] = 0 then begin то алгоритм очевидно будет работать от определения простого числа... |