Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 14
Таблицы не хватает в конце с итогами по времени.
А так, зачетно.
А так, зачетно.
Время работы: 26 минут 30 секунд
А без Console.WriteLine сколько будет?
То же самое время. 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
При этом решето Сундарама вычеркивает числа вида n = i +J +2ij.
разве для i=1 и j=2 мы не вычеркнем число 7.
требование для 2i+1 — простое число также выполняется.
может есть еще какие-то неозвученные границы применимости?
В решете Сундарама мы вычеркиваем числа i + j + 2ij для любых i, j (не только простых), для оставшихся чисел 2n+1 — будет простое число, не 2i+1. То есть, число 7 мы вычеркнем правильно, потому что 2*7+1=15 не является простым числом. У меня было написано ni, я исправил на n, надеюсь, так понятней будет
Еще одно полезное свойство таких программ — можно проверять стабильность работы системы, потому что результат заранее известен.
Здесь приведена недостоверная информация по решету Аткина. Оно обладает значительно лучшей оценкой. А основан алгоритм Аткина на том, что существует возможность перебора нужных значений квадратичных форм с использованием подходящих шагов по x и y, и полный перебор их значений не требуется.
Можно цитату, какая именно информация, приведенная здесь, является недостоверной?
«Практическая реализация» использует теоремы Аткина, но не является реализацией его алгоритма.
А, теперь понял суть ваших претензий. Мне кажется, это вопрос терминологии, какой именно алгоритм является «классическим» решетом Аткина, а какой — его оптимизированной версией. Мой вариант — такой же, как и в статье в Википедии, хотя в дискуссии к ней он тоже критикуется.
Алгоритм Аткина приведен в его статье, поэтому это не вопрос терминологии. При фаторизации (2,3,5) будет справедливо следующее. Если (x0,y0) являются «подходящими» значениями для первой квадратичной формы, то значения (x0+15, y0) и (х0, y0+30) тоже будут для нее «подходящими». И такой шаг является минимальным. Это позволит вам представить разницу в быстродействии решета Аткина и реализации, приведенной в публикации.
В его статье приведены оба варианта: в главе 3 «Prime sieves using irreducible binary quadratic forms» — аналогичный приведенному здесь и в википедии, и в главе 4 «Enumerating lattice points» — его оптимизация до O(n / log log n).
В любом случае, именно алгоритм, приведенный в публикации, в Википедии называется решетом Аткина, хотя многие, действительно, с этим не согласны.
К тому же, я в публикации упоминаю утилиту primegen, основанную на оптимизированном решете Аткина, которая в 30 раз быстрее моей реализации.
В любом случае, именно алгоритм, приведенный в публикации, в Википедии называется решетом Аткина, хотя многие, действительно, с этим не согласны.
К тому же, я в публикации упоминаю утилиту primegen, основанную на оптимизированном решете Аткина, которая в 30 раз быстрее моей реализации.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Ищем простые числа до триллиона за тридцать минут