|
|
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
Существует-ли такой ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.06.2007, 10:37 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
Все в числе, на интервале значений чисел? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.06.2007, 10:45 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
qwedfgСуществует-ли такой ? Да. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.06.2007, 11:00 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
1) Для ограниченного диапазона применяют Решето Эратосфена. (Требует дополнительной памяти в виде битовой карты, соизмеримой с диапазоном). 2) Для монотонной последовательности простых чисел (ППЧ) я писал довольно шустрый алгоритм на С++. Могу поискать, если интересно. Правда он работает в диапазоне 32-разрядных целых. А при переходе в более высокую разрядную сетку нужно скачкообразно менять технологию и поэтому на дальнейшие оптимизации я забил. Вообще, спустя много лет, я понял, что затея с написанием универсального алгоритма генерации последовательности простых чисел - из области поиска "философского камня" . Можно достичь успеха в любых смежных с ней областях (теория чисел, криптография) но сам метод будет всегда в состоянии бета-версии. Кстати, проводить соревнования по скорости числогенерации - бесполезное занятие, поскольку финишная черта - находится в бесконечности, а именно там и проявляют себя основные свойства ППЧ. И алгоритм, который на старте дал приличную скорость, в более серъезном диапазоне может полностью провалится (на радость математикам и в назиданиие любителям кодировать в АСМ-е ). 3) Если нужно просто сгенерировать одно простое число (ОООЧЕНЬ БОЛЬШОЕ), используются генерация случайного числа с проверкой его на простоту специальными быстрыми тестами. Они гарантируют "простоту" с очень высокой вероятностью 99.9999... Этот метод используют в криптографии. ---------------- С уважением ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.06.2007, 11:17 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
qwedfgСуществует-ли такой ?один из первых известных - "решето эратосфена" http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BE_%D0%AD%D1%80%D0%B0%D1%82%D0%BE%D1%81%D1%84%D0%B5%D0%BD%D0%B0 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.06.2007, 11:20 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
qwedfg wrote: > Существует-ли такой ? Да. Поройтесь на википедии и поищите гуглом, я где-то (вроде бы в википедии) видел несколько элегантных алгоритмов, более интересных, чем "решето". К сожалению, найти пока не могу, где это было. Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.06.2007, 12:40 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
Для маленьких чисел можно применить табличный метод, используя уже найденные числа :) А если придумать хороший алгоритм, можно неплохо подзаработать ;) так что, автор- дерзай! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.06.2007, 19:56 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
могу дать почту одного человека, он находил простые числа вроде б от 1 до десятков миллионов и довольно быстро. если не ошибаюсь, за час примерно. аффтопитезь: 4 8 15 16 23 42 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.07.2007, 10:36 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
Вот простая генерилка. Не использует дополнительную память. На моём Celeron 1.7 Ghz выдаёт за 5 секунд все числа в диапазоне от 3 до 1000000. Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.07.2007, 16:40 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
Если for(int i=2;i<=ub;i++) заменить на for(int i=2;i<=ub;i+=2) То будет уже в два раза шустрее ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.07.2007, 20:00 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
Для каких целей нужны простые числа автору? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.07.2007, 20:04 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
IcyCoolЕсли for(int i=2;i<=ub;i++) заменить на for(int i=2;i<=ub;i+=2) То будет уже в два раза шустрееТ.е. делимость на 3 предлагате не проверять? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.07.2007, 20:55 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
qwedfg wrote: > Существует-ли такой ? Был хороший простой двоичный алгоритм нахождения простых чисел, очень быстрый. Проблема: забыл, где видел и как называется :-( Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.07.2007, 21:31 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
Есть такая теоремка: Пусть Х - тестируемое число. Если A^X mod X = А для всех A = 2 ... X-1, то X - простое. На практике ограничиваются несколькими выборочными проверками, т.к. подобные тесты пропускают мизерный процент "псевдопростых" чисел. Для чисел специального вида существуют хитрые и точные методы. Тут уже нужно подробнее узнать о целях автора! --- Идеи движут Мир! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.07.2007, 14:24 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
Генерируется случайное нечётное большое число и проверятся, например, с помощью вероятностного теста Миллера - Рабина ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.08.2007, 09:21 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
кроме перебора - не существует ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.08.2007, 14:30 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
Хитроглазыйкроме перебора - не существует Я - бы не стал торопится с таким заявлением. К примеру, если вам известена монотонная последовательность простых чисел (2,3,5,7,11,13) то найти следующее простое число довольно просто. Можно перемножить числа последовательности и добавить 1. Этот метод - не переборный. Например: 2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 Это число простое по определению. Правда, этот метод не даёт возможности найти числа в окрестности выше 13. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.08.2007, 15:01 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
Хитроглазыйкроме перебора - не существует Перебор - самый "тупой" и громоздкий способ. Уже для 100-значных чисел потребовалось бы много машино-лет на перебор всех делителей до 10^50. А рекорд сейчас - 9,808,358 знаков! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.08.2007, 10:18 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
mayton2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 Это число простое по определению 30031 = 59*509 и ага ;) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.08.2007, 12:02 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
mayton К примеру, если вам известена монотонная последовательность простых чисел (2,3,5,7,11,13) то найти следующее простое число довольно просто. Можно перемножить числа последовательности и добавить 1. Этот метод - не переборный. Например: 2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 Это число простое по определению.в формулировке пропущена часть. "пердположим, известны _все_ простые числа..." далее - было бы по тексту. И вообще говоря - это всего лишь фрагмент доказательства бесконечного числа простых чисел. В силу отказа от предположения о конечности и известности алгоритм не верен. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.08.2007, 12:36 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
Хитроглазый wrote: > 30031 = 59*509 и ага ;) очевидно, имелось в виду правило Натуральное p > 1 является простым тогда и только тогда, когда (p - 1)! + 1 делится на p Только это тест. А как насчет 2^(2^n)+1 ? и вот: http://www.codenet.ru/progr/alg/Simple-Numbers.php Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.08.2007, 12:39 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
Хитроглазый30031 = 59*509 и ага ;) Верно! Вы меня подловили. Ваш ник вам - соответствует. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.08.2007, 12:56 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
mayton wrote: > Верно! Вы меня подловили. > > Ваш ник вам - соответствует. Нашел-таки я тот алгоритм, о котором раньше писал. 2^n-1 (http://ru.wikipedia.org/wiki/Число_Мерсенна) Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.08.2007, 12:57 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
ErV wrote: > (http://ru.wikipedia.org/wiki/Число_Мерсенна) И довесок. http://ru.wikipedia.org/wiki/Тест_Люка_?_Лемера Млин. это не тот алгоритм... Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.08.2007, 12:59 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
господа кодеры, а для Borland 3.1 можно вас попросить код написать? а то задачку хитрую задали... написать программу нахождения n пар простых чисел разница между которыми равна 2, иначе называемых "близнецами", т.е. 3 и 5, 5 и 7, 11 и 13... как пример... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.10.2008, 23:26 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
Nikolay B. qwedfgСуществует-ли такой ? Да. НЕТ для малых чисел - решето Эратосфена для больших вероятностные тесты в общем случае берется произвольное число, затем в любую сторону шлепается до тех пор, пока не найдется простое. в реальности количество шагов (СРЕДНЕЕ) имеет зависимость, (только среднее!) вроде логарифма. (среднее, т.е. если надо найти К чисел друг за другом). в отдельном случае количество шагов не определено. есть gnu mp библиотека (на сегодня самая быстрая для многих платформ), там есть ген больших чисел. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.10.2008, 10:04 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
BeastIvгоспода кодеры, а для Borland 3.1 можно вас попросить код написать? а то задачку хитрую задали... написать программу нахождения n пар простых чисел разница между которыми равна 2, иначе называемых "близнецами", т.е. 3 и 5, 5 и 7, 11 и 13... как пример... борланд мертв в вашем случае - найти одно число и проверить n+2 на простоту. никак иначе ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.10.2008, 10:06 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
Если реализация конкретных алгоритмов интересуют, то можно посмотреть исходные тексты функций в пакетах Mathematica и Maple ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.10.2008, 22:07 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
как определить более-менее оптимально что число простое? нутром чую что не надо пробегать от 2 до n-1 и делить, так как уже выше н/2 это заведомо будет чтото дробное с единицей в целой части. Еще какие приколы? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.04.2010, 23:16 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
вот алгоритм мой (простейший, зато верный) Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.04.2010, 00:10 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
даже так Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.04.2010, 00:10 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
Делители в диапазоне от 2 до корня квадратного от val. И четные выше двух не учитывать. И тройки выше трёх не учитывать. И пятёрки... короче ты понял. Направлений в оптимизации - масса. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.04.2010, 00:15 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
ну четные еще можно пожалуй более оптимально определить чем поделить, но тройки, пятерки и так далее непонятно как. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.04.2010, 00:30 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
+=3 && +=5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.04.2010, 00:43 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
не понял ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.04.2010, 00:46 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
простое число делится только на 1 и на само себя без остатка, значит не делится на 2,3,5,7,11,13... и т.д. тоесть не делится на теже простые числа, тоесть чтобы найти следующее простое число, - надо просто проверить неделится ли оно на все предыдущие найденные прост. числа.. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.04.2010, 16:08 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
вот предельно простой вариант поиска прост. чисел, т.к. все простые числа в памяти хранить неполучится, то они/результат сохраняеются в файл, и при следующем запуске продолжается поиск с последнего найденного числа, правда тут размер числа ограничен всего 32 битами, хотя с таким поиском и перебором за этот предел будет сложно уйти.. )) Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113. 114. 115. 116. 117. 118. 119. 120. 121. 122. 123. 124. 125. 126. 127. 128. 129. 130. 131. 132. 133. 134. 135. 136. 137. 138. 139. 140. 141. 142. 143. 144. 145. 146. 147. 148. 149. 150. 151. 152. 153. 154. 155. 156. 157. 158. 159. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.04.2010, 16:47 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
zloyGamer, а зачем ты объявил isSimpleLongCheck но нигде её не используешь? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.04.2010, 17:49 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
BeastIvгоспода кодеры, а для Borland 3.1 можно вас попросить код написать? а то задачку хитрую задали... написать программу нахождения n пар простых чисел разница между которыми равна 2, иначе называемых "близнецами", т.е. 3 и 5, 5 и 7, 11 и 13... как пример... Звучит примерно как "ану-ка, холопы, настреляйте мне дичи из этого мушкета. Не пановское это дело по лесам бегать". ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.04.2010, 18:56 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
zloyGamerпростое число делится только на 1 и на само себя без остатка, значит не делится на 2,3,5,7,11,13... и т.д. тоесть не делится на теже простые числа, тоесть чтобы найти следующее простое число, - надо просто проверить неделится ли оно на все предыдущие найденные прост. числа.. это допер, но эти числа надо тогда хранить что не правильно (во всяком случае мне не подходит) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.04.2010, 22:44 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
Нахождение больших простых чисел простым перебором/тестом занимает много м.-времени, поэтому самое простое, что приходит в голову - это уменьшить число операций цикла за счет фильтра последовательности чисел (Метод от обратного). Т.е. сразу исключать числа из проверки, которые обладают свойствами не "простого" числа: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. Тогда в любой десятке последовательности чисел для теста останется значительно меньше чисел, тем самым можно резко и значительно уменьшить м.-время нахождения массива больших простых чисел. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.04.2010, 22:59 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
AIS, и как ты предлагаешь сумму цифр к примеру посчитать? или узнать что число делится на 5 не деля? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.04.2010, 23:12 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
ПетросъянAIS, и как ты предлагаешь сумму цифр к примеру посчитать? или узнать что число делится на 5 не деля? Это свойства чисел. В частности, если последняя цифра (это видно в примере) равна нулю либо 5, то число делется на 5. Это во-первых. А во-вторых, это одно действие, а пробежаться с тестом на "деление" по всему массиву уже найденных простых чисел - гораздо дольше. ;) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.04.2010, 23:20 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
AISПетросъянAIS, и как ты предлагаешь сумму цифр к примеру посчитать? или узнать что число делится на 5 не деля? Это свойства чисел. В частности, если последняя цифра (это видно в примере) равна нулю либо 5, то число делется на 5. Это во-первых. А во-вторых, это одно действие, а пробежаться с тестом на "деление" по всему массиву уже найденных простых чисел - гораздо дольше. ;) ты мне код приведи быстрой проверки делимости на 5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.04.2010, 23:24 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
AIS Это свойства чисел. В частности, если последняя цифра (это видно в примере) равна нулю либо 5, то число делется на 5. Промах. Ты повторяешь мои ошибки. Признаки делимости на 3,5,9 и т.д. для ДЕСЯТИЧНЫХ чисел не имеют никакого практического полезного эффекта если проверяемое число хранится в ДВОИЧНОЙ. Проверка на операцию '%' будет эффективнее. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.04.2010, 23:27 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
Петросъянэто допер, но эти числа надо тогда хранить что не правильно (во всяком случае мне не подходит) Совсем не обязательно хранить все числа. Но если организовать кеш хотя-бы до тысячи, то можно довольно эффективно отбрасывать уже проверенные, при условии что нагрузка на функцию isSimple будет довольно большой. В прошлом году в форуме был довольно плотный тред на эту тему и если вы не поленитесь то найдете немало интересного на тему решета Эратосфена и оптимального хранения чисел в кеше. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.04.2010, 23:40 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
Петросъян , а вообще - это была идея/предложение/совет/мысль в слух/направление поиска решения. Я так полагаю, что это можно назвать и "алгоритмом". А создавать далее скрипт, как то не хочется. Gluk (Kazan)Звучит примерно как "ану-ка, холопы, настреляйте мне дичи из этого мушкета. Не пановское это дело по лесам бегать". Золотые слова. maytonПромах. Ты повторяешь мои ошибки. Признаки делимости на 3,5,9 и т.д. для ДЕСЯТИЧНЫХ чисел не имеют никакого практического полезного эффекта если проверяемое число хранится в ДВОИЧНОЙ. Проверка на операцию '%' будет эффективнее. Промах, согласен, проглядел где-то что "хранится в ДВОИЧНОЙ". ;) А в остальном не согласен. Если с десятичными числами можно достигнуть необходимого эффекта (скорость получения результата), то уже из массива простых чисел в десятичном виде перевести в двоичный - много времени и сил не займет. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.04.2010, 23:41 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
maytonПетросъянэто допер, но эти числа надо тогда хранить что не правильно (во всяком случае мне не подходит) Совсем не обязательно хранить все числа. Но если организовать кеш хотя-бы до тысячи, то можно довольно эффективно отбрасывать уже проверенные, при условии что нагрузка на функцию isSimple будет довольно большой. В прошлом году в форуме был довольно плотный тред на эту тему и если вы не поленитесь то найдете немало интересного на тему решета Эратосфена и оптимального хранения чисел в кеше. в общем случае выигрыш этого улучшательства будет стремиться к бесконечносит ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.04.2010, 23:52 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
AIS Петросъян , а вообще - это была идея/предложение/совет/мысль в слух/направление поиска решения. Я так полагаю, что это можно назвать и "алгоритмом". А создавать далее скрипт, как то не хочется. Gluk (Kazan)Звучит примерно как "ану-ка, холопы, настреляйте мне дичи из этого мушкета. Не пановское это дело по лесам бегать". Золотые слова. maytonПромах. Ты повторяешь мои ошибки. Признаки делимости на 3,5,9 и т.д. для ДЕСЯТИЧНЫХ чисел не имеют никакого практического полезного эффекта если проверяемое число хранится в ДВОИЧНОЙ. Проверка на операцию '%' будет эффективнее. Промах, согласен, проглядел где-то что "хранится в ДВОИЧНОЙ". ;) А в остальном не согласен. Если с десятичными числами можно достигнуть необходимого эффекта (скорость получения результата), то уже из массива простых чисел в десятичном виде перевести в двоичный - много времени и сил не займет. тип оф зи дей: в компе все в двоичной. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.04.2010, 23:53 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
Петросъян...в компе все в двоичной. А я так глубоко не заглядываю. ;) Но полагаю, что с двоичными по предложенному методу, тоже можно получить эффект в сравнении с простым перебором всех значений. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.04.2010, 00:08 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
AISЕсли с десятичными числами можно достигнуть необходимого эффекта (скорость получения результата), то уже из массива простых чисел в десятичном виде перевести в двоичный - много времени и сил не займет. Эта мысль заведёт тебя в тупик. Сама по себе операция перехода между базисами имеет вычислительную сложность. А производительность для алгоритмов prime-детектирования и факторизации - это самое главное. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.04.2010, 00:16 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
maytonzloyGamer, а зачем ты объявил isSimpleLongCheck но нигде её не используешь? isSimpleLongCheck - проверяет делится ли число X на любое из чисел от 2 до X-1 простым перебором, если так проверять каждое число то на поиск уйдет довольно много времени., но этйо функцией я проверял свою дествительно ли: zloyGamer"чтобы найти следующее простое число, - надо просто проверить неделится ли оно на все предыдущие найденные прост. числа.." Петросъянэто допер, но эти числа надо тогда хранить что не правильно (во всяком случае мне не подходит) нет, иначе алгоритмы определения/поиска будут тратить на этоже дело гораздо больше времени, поэтому самое оптимальное хранить эти числа и с ними сравнивать, вот только как их хранить чтоб потом быстро выбирать/добавлять, - проблема тока в реализации. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.04.2010, 01:37 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
zloyGamer, A ut kuda vziat QFile i QByteArray. U menia bez nix oshibki vydayut ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.04.2010, 10:51 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
zhenga, он использовал QT framework. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.04.2010, 12:52 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
mayton, привет. можете дать программу нахождения самого большого числа? мой msergeyj@mail.ru буду благодарен=) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.11.2011, 07:20 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
серегй, Вообще самого большого простого? Как бэ никто не доказал еще, что ряд простых - конечен... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.11.2011, 09:29 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
Сергей, самое большое простое число известное науке входит в множество простых чисел Мерсена. Ищите в wiki там много материала. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.11.2011, 10:43 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
AndreTM, не самое большое, а большое простое число которое можно найти на простом пк. мне бы алгоритм нахождения на с++ кто нибудь помогите ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.11.2011, 12:30 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
mayton, вы там написали что можете дать программу для нахождения "самого большого простого числа" если можно я бы хотел посмотреть=) msergeyj@mail.ru это моя почта. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.11.2011, 12:33 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
Не мог я такого написать. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.11.2011, 12:37 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
zloyGamer, хай zloyGamer а вы что думайте? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.11.2011, 12:58 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
серегйAndreTM, не самое большое, а большое простое число которое можно найти на простом пк. Вообще-то, последнее "самое большое простое Мерсенна" и было найдено "на простом ПК" два года назад. http://mersenne.org Даже если вы подразумеваете, что-то типа "надо найти на простом (?) ПК наибольшее возможное простое с помощью " решета Эратосфена ", то и в этом случае необходимо привести хотя бы характеристики этого вашего ПК, а также ожидаемое возможное время на расчет... В противном случае, ваш вопрос не имеет смысла. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.11.2011, 20:07 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
AndreTM, ну обычный двухядерный ноут=) мне главное чтоб было на диапазоне 32. лонг инт кажеться. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.11.2011, 03:02 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
серегйну обычный двухядерный ноут=) мне главное чтоб было на диапазоне 32. лонг инт кажеться. 2**31-1 устроит? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.11.2011, 07:01 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
Изопропил, угу ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.11.2011, 07:46 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
серегй, Так сложно искать? http://ru.wikipedia.org/wiki/Решето_Эратосфена http://how2.org.ua/art/124 http://easy-coding.blogspot.com/2010/03/go-c-c.html http://olympbrain.com/theory/resheto.aspx ... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.11.2011, 13:47 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
серегйAndreTM, ну обычный двухядерный ноут=) мне главное чтоб было на диапазоне 32. лонг инт кажеться. В принципе, эратосфенить можно до бесконечности при любой разрядности процессора. Разве что, закончится оперативная память. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.11.2011, 14:16 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
AndreTMсерегй, Вообще самого большого простого? Как бэ никто не доказал еще, что ряд простых - конечен...Мало того, как бэ давно доказано, что он бесконечен, разве нет?.. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.11.2011, 16:23 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
Ну, если Сергей поставит себе на борт 8Г памяти, это будет 8Г = 8192М = 8388608K = 8589934592 байт = 68 719 476 736 бит информации. Это же число будет задавать диапазон для метода Эратосфена. Для простоты будем считать что ОС не в счёт. Самое (почти) большое число Мерсена (на 6 ноября 2011 г) по данным wiki: там же пишут что это число имеет 12 978 189 десятичных разрядов против наших 11 разрядов эратосфена на типовой рабочей станции. Тоесть "эратосфенить" для поиска наибольшего простого числа не имеет смысла. Имеет смысл генерить числа Мерсена и делать максимально-быстрые тесты на простоту. Но в этом случае мы пропускаем другие простые числа которые находятся между числами Мерсена. Просто прыгаем вперёд очень быстро. Кст. Эратосфен невыгоден с точки зрения хранения. На больших значениях бит-карта будет заполнена нулями с редкими вкраплениями единиц. Поэтому поиск максимально большого простого числа в диапазоне чисел или просто поиск макс. большого простого числа известного науке - это разные задачи. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.11.2011, 16:54 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
mayton, учту=) еще кто что думает? у кого ни будь есть примеры программы? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.11.2011, 10:57 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
хто та из великих доказал еще в школе, что самого большого не существует :-) доказательство тривиально, могу привести :-) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.11.2011, 12:13 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
Aklin...могу привести :-) Давай. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.11.2011, 13:04 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
ShSerge, я не ищу именно самое большое число а то число кторое можно найти на моем ноуте используя С++ ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.11.2011, 01:11 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
Точную ссылку не помню но посмотри отсюдова 7164978 назад и вперёд. Там много исходников. Почти работают на обычных раб-станциях с 1Г оперативки. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.11.2011, 01:27 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
mayton, ого круто=) кое че нашел! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.11.2011, 07:56 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
qwedfgСуществует-ли такой ? Решение этого задания есть тут: Задачи на числа. Решение. Покритикуйте. (часть №1) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.04.2012, 18:34 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
Удивительно живучая тема, судя по количеству поднятий через интервал более года. Простые числа волнуют умы и сердца молодых программеров. :) серегйне самое большое, а большое простое число которое можно найти на простом пк. серегй, если не секрет, а зачем оно тебе, и что ты с ним будешь делать? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.04.2012, 22:44 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
mayton, Код: javascript 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. Так оно будет на ECMAScript 5. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.05.2012, 17:16 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
Кстати, нафига я считал margin - вообще непонятно. Выбрасываем. Код: javascript 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.05.2012, 17:20 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
Division X, не проблема найти простые числа, проблема найти их быстро))). Правильный алгоритм должен начинаться со слова "решето" ИМХО ;) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.05.2012, 17:57 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
kDnZPDivision X, не проблема найти простые числа, проблема найти их быстро))). Правильный алгоритм должен начинаться со слова "решето" ИМХО ;) Ну а это что, по-твоему? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.05.2012, 18:00 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
Надеюсь, не надо расшифровывать, что такое some и push? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.05.2012, 18:02 |
|
||
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#18+
kDnZPПравильный алгоритм должен начинаться со слова "решето" ИМХО ;) kDnZP-compatible version: Код: javascript 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.05.2012, 18:12 |
|
||
|
|

start [/forum/topic.php?all=1&fid=16&tid=1342169]: |
0ms |
get settings: |
5ms |
get forum list: |
14ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
158ms |
get topic data: |
7ms |
get forum data: |
2ms |
get page messages: |
62ms |
get tp. blocked users: |
2ms |
| others: | 202ms |
| total: | 458ms |

| 0 / 0 |
