|
|
|
Алгоритм нахождения простых чисел
|
|||
|---|---|---|---|
|
#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 |
|
||
|
|

start [/forum/topic.php?fid=16&msg=36572587&tid=1342169]: |
0ms |
get settings: |
8ms |
get forum list: |
16ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
168ms |
get topic data: |
10ms |
get forum data: |
2ms |
get page messages: |
68ms |
get tp. blocked users: |
1ms |
| others: | 219ms |
| total: | 498ms |

| 0 / 0 |
