Comments 14
Таблицы не хватает в конце с итогами по времени.
А так, зачетно.
А так, зачетно.
+3
Время работы: 26 минут 30 секунд
А без Console.WriteLine сколько будет?
0
То же самое время. Console.WriteLine вызывается, только если новое расстояние больше уже найденного, и так как максимальное расстояние равно 540, будет вызываться очень редко (около 50 раз)
полный вывод программы
2 — 0 = 2
11 — 7 = 4
29 — 23 = 6
97 — 89 = 8
127 — 113 = 14
541 — 523 = 18
907 — 887 = 20
1151 — 1129 = 22
1361 — 1327 = 34
9587 — 9551 = 36
15727 — 15683 = 44
19661 — 19609 = 52
31469 — 31397 = 72
156007 — 155921 = 86
360749 — 360653 = 96
370373 — 370261 = 112
492227 — 492113 = 114
1349651 — 1349533 = 118
1357333 — 1357201 = 132
2010881 — 2010733 = 148
4652507 — 4652353 = 154
17051887 — 17051707 = 180
20831533 — 20831323 = 210
47326913 — 47326693 = 220
122164969 — 122164747 = 222
189695893 — 189695659 = 234
191913031 — 191912783 = 248
387096383 — 387096133 = 250
436273291 — 436273009 = 282
1294268779 — 1294268491 = 288
1453168433 — 1453168141 = 292
2300942869 — 2300942549 = 320
3842611109 — 3842610773 = 336
4302407713 — 4302407359 = 354
10726905041 — 10726904659 = 382
20678048681 — 20678048297 = 384
22367085353 — 22367084959 = 394
25056082543 — 25056082087 = 456
42652618807 — 42652618343 = 464
127976335139 — 127976334671 = 468
182226896713 — 182226896239 = 474
241160624629 — 241160624143 = 486
297501076289 — 297501075799 = 490
303371455741 — 303371455241 = 500
304599509051 — 304599508537 = 514
416608696337 — 416608695821 = 516
461690510543 — 461690510011 = 532
614487454057 — 614487453523 = 534
738832928467 — 738832927927 = 540
Processed primes up to 1,000,000,000,000 in 00:26:23.3155338: Max Distance=540
11 — 7 = 4
29 — 23 = 6
97 — 89 = 8
127 — 113 = 14
541 — 523 = 18
907 — 887 = 20
1151 — 1129 = 22
1361 — 1327 = 34
9587 — 9551 = 36
15727 — 15683 = 44
19661 — 19609 = 52
31469 — 31397 = 72
156007 — 155921 = 86
360749 — 360653 = 96
370373 — 370261 = 112
492227 — 492113 = 114
1349651 — 1349533 = 118
1357333 — 1357201 = 132
2010881 — 2010733 = 148
4652507 — 4652353 = 154
17051887 — 17051707 = 180
20831533 — 20831323 = 210
47326913 — 47326693 = 220
122164969 — 122164747 = 222
189695893 — 189695659 = 234
191913031 — 191912783 = 248
387096383 — 387096133 = 250
436273291 — 436273009 = 282
1294268779 — 1294268491 = 288
1453168433 — 1453168141 = 292
2300942869 — 2300942549 = 320
3842611109 — 3842610773 = 336
4302407713 — 4302407359 = 354
10726905041 — 10726904659 = 382
20678048681 — 20678048297 = 384
22367085353 — 22367084959 = 394
25056082543 — 25056082087 = 456
42652618807 — 42652618343 = 464
127976335139 — 127976334671 = 468
182226896713 — 182226896239 = 474
241160624629 — 241160624143 = 486
297501076289 — 297501075799 = 490
303371455741 — 303371455241 = 500
304599509051 — 304599508537 = 514
416608696337 — 416608695821 = 516
461690510543 — 461690510011 = 532
614487454057 — 614487453523 = 534
738832928467 — 738832927927 = 540
Processed primes up to 1,000,000,000,000 in 00:26:23.3155338: Max Distance=540
+1
При этом решето Сундарама вычеркивает числа вида n = i +J +2ij.
разве для i=1 и j=2 мы не вычеркнем число 7.
требование для 2i+1 — простое число также выполняется.
может есть еще какие-то неозвученные границы применимости?
+1
В решете Сундарама мы вычеркиваем числа i + j + 2ij для любых i, j (не только простых), для оставшихся чисел 2n+1 — будет простое число, не 2i+1. То есть, число 7 мы вычеркнем правильно, потому что 2*7+1=15 не является простым числом. У меня было написано ni, я исправил на n, надеюсь, так понятней будет
0
Еще одно полезное свойство таких программ — можно проверять стабильность работы системы, потому что результат заранее известен.
+3
Здесь приведена недостоверная информация по решету Аткина. Оно обладает значительно лучшей оценкой. А основан алгоритм Аткина на том, что существует возможность перебора нужных значений квадратичных форм с использованием подходящих шагов по x и y, и полный перебор их значений не требуется.
0
Можно цитату, какая именно информация, приведенная здесь, является недостоверной?
0
«Практическая реализация» использует теоремы Аткина, но не является реализацией его алгоритма.
0
А, теперь понял суть ваших претензий. Мне кажется, это вопрос терминологии, какой именно алгоритм является «классическим» решетом Аткина, а какой — его оптимизированной версией. Мой вариант — такой же, как и в статье в Википедии, хотя в дискуссии к ней он тоже критикуется.
0
Алгоритм Аткина приведен в его статье, поэтому это не вопрос терминологии. При фаторизации (2,3,5) будет справедливо следующее. Если (x0,y0) являются «подходящими» значениями для первой квадратичной формы, то значения (x0+15, y0) и (х0, y0+30) тоже будут для нее «подходящими». И такой шаг является минимальным. Это позволит вам представить разницу в быстродействии решета Аткина и реализации, приведенной в публикации.
0
В его статье приведены оба варианта: в главе 3 «Prime sieves using irreducible binary quadratic forms» — аналогичный приведенному здесь и в википедии, и в главе 4 «Enumerating lattice points» — его оптимизация до O(n / log log n).
В любом случае, именно алгоритм, приведенный в публикации, в Википедии называется решетом Аткина, хотя многие, действительно, с этим не согласны.
К тому же, я в публикации упоминаю утилиту primegen, основанную на оптимизированном решете Аткина, которая в 30 раз быстрее моей реализации.
В любом случае, именно алгоритм, приведенный в публикации, в Википедии называется решетом Аткина, хотя многие, действительно, с этим не согласны.
К тому же, я в публикации упоминаю утилиту primegen, основанную на оптимизированном решете Аткина, которая в 30 раз быстрее моей реализации.
+1
Sign up to leave a comment.
Ищем простые числа до триллиона за тридцать минут