Модифицировать программу (практическая помощь)

[Nataly-Mak]

Работает программа whitefox



Генерация простых в интервале длины 2 млрд не более 4 сек, проверка построения квадрата - минута с хвостиком.

[maxal]

Nataly-Mak в сообщении #905731 писал(а):

Генерация простых в интервале длины 2 млрд не более 4 сек, проверка построения квадрата - минута с хвостиком.

Что и требовалось доказать: при нормальном генераторе (будь то primesieve или что-то еще) основная вычислительная нагрузка ложиться на построение квадрата.

[Alexu007]

2 млрд за 4 секунды на обычном компьютере (у меня шустрый ноутбук) - это реально? Пустой цикл из 2-х миллиардов, который ничего не делает - дольше выполняться будет...

[Nataly-Mak]

maxal в сообщении #905739 писал(а):

Nataly-Mak в сообщении #905731 писал(а):

Генерация простых в интервале длины 2 млрд не более 4 сек, проверка построения квадрата - минута с хвостиком.

Что и требовалось доказать: при нормальном генераторе (будь то primesieve или что-то еще) основная вычислительная нагрузка ложиться на построение квадрата.

Дуб да мочало - начинай сначала

Вы сначала докажите, что у вас нормальный генератор.
В чём я очень сильно сомневаюсь, судя по времени, которое вы затратили на поиск ассоциативного квадрата Стенли 4-го порядка. Что у вас в этом поиске с алгоритмом построения квадрата было не так, как у Progger, например?? Или у whitefox.

Вы уже оттестировали свой генератор? Результаты теста в студию!

И вы не ответили на мой вопрос: какая из двух программ - с генератором svb или с генератором primesieve при одинаковой процедуре проверки построения квадрата - будет работать быстрее

-- Вт сен 09, 2014 08:51:27 --

Alexu007 в сообщении #905748 писал(а):

2 млрд за 4 секунды на обычном компьютере (у меня шустрый ноутбук) - это реально? Пустой цикл из 2-х миллиардов, который ничего не делает - дольше выполняться будет...

Alexu007
вы тему читаете?

Progger в сообщении #905172 писал(а):

По поводу скорости работы. Для сборки использовался компилятор gcc-4.9 с опцией -O3. Измерялось на ноуте с поцессором Intel(R) Core(TM)2 Duo CPU T6600 @ 2.20GHz. Генерация простых чисел в диапазоне $0..10^{10}$ занимает 5.82 сек. Вместе с поиском квадрата 4-го порядка - 45.23 сек, 5-го порядка - 154.08 сек.

Прочитайте, цитату, пожалуйста.
Вам подчеркнуть "генерация простых чисел в диапазоне $0..10^{10}$ занимает 5.82 сек" или сами найдёте?

У меня компьютер не шустрый, даже тихоход.
Программа whitefox, как я уже писала, выводит на экран время каждые две секунды. Так вот, генерация длится два таких вывода времени - раз: 2 секунды, два - ещё 2 секунды. И сразу же начинается процедура проверки построения квадрата, пишется слово "Проверено". При генерации простых чисел на экране пишется слово "Просеяно".

Цитата:

Видно, что большую часть времени занимает процедура проверки, что позволяет надеяться на значительное ускорение работы за счёт улучшения алгоритма проверки.

maxal
ещё раз не пишите "что и требовалось доказать", ладно?
Вот именно: это и доказывает, что генератор primesieve сверхскоростной, что я и пытаюсь всем здесь доказать.

Теперь перед всеми стоит задача оптимизации процедуры проверки построения квадрата Стенли 5-го порядка.
Так давайте, вместо пустых споров, займёмся решением этой задачи.

-- Вт сен 09, 2014 09:08:49 --

Alexu007
вы видите на экране в окне программы запись "Скорость 109"?
Это скорость проверки в млрд/час (натуральных чисел) для текущего интервала. Уже объясняла для Dmitry40 (что вы, похоже, тоже не читали).
Если арифметические вычисления умеете выполнять, посчитайте, сколько секунд в среднем потребуется для обработки 2 млрд натуральных чисел (сюда войдёт и генерация простых чисел и процедура проверки построения квадрата).

-- Вт сен 09, 2014 09:26:37 --

Приводила и отчёт о работе программы svb, да, видно, это вообще никто не читал.
Приведу ещё раз (интервал тот же самый, для которого у меня сейчас работает программа whitefox ):

5: 673401999227921..673402499227920
Sieve time: 28.83 sec
si=0,0,0
Searching time: 4.69 sec
number=14646392
Time: 33.53 sec

Как я понимаю: время генерации простых - 28.83 сек. (это на полмиллиарда!); время проверки построения квадрата 4.69 сек. Общее время за цикл - 33.53 сек.

Сравнивайте!

Похоже, svb хорошо справился с процедурой проверки построения квадрата - она у него выполняется в несколько раз быстрее генерации простых.

[Nataly-Mak]

Кстати, ссылка на тему "Программа генерации КПППЧ" на форуме ПЕН:
http://e-science.ru/?q=node/145280

В теме довольно подробно написано о КПППЧ (Комплементарные Пары Последовательных Простых Чисел).
Можно найти там, что попутно надо искать.

Dmitry40 нашёл первую 22-ку (набор из 11 комплементарных пар последовательных простых чисел). Это решение внесено в OEIS - A055381. Теперь можно искать 24-ку.
Пока никто не нашёл первую 15-ку (это набор из 7 комплементарных пар последовательных простых чисел с центральным числом, которое равно половине константы комплементарности набора). Это для A055380.

Ну, и не надо забывать о наборах из 8 комплементарных пар последовательных простых, среди которых может оказаться второй ассоциативный квадрат Стенли 4-го порядка.

Написала об этой проблеме на форуме сайта своего коллеги Stefano Tognon (ice00):
http://primesmagicgames.altervista.org/ ... /#post-222
Знаю, что этот форум просматривает Jarek; хотелось бы привлечь его внимание к этой проблеме.
Ещё собираюсь написать Jens K Andersen; может быть, он захочет поучаствовать в решении этой задачи, хотя знаю, что он очень пессимистически оценил возможность её решения.

[Nataly-Mak]

Ещё интересная задача

Цитата:

For d=5 the square with minimal index has difference 222.
Here is a square with the smaller difference 180:

13 19 43 109 139
31 37 61 127 157
41 47 71 137 167
53 59 83 149 179
67 73 97 163 193

However, the minimal difference for an admissible pattern is 156, for example for this pattern:

0 10 24 40 54
12 22 36 52 66
60 70 84 100 114
96 106 120 136 150
102 112 126 142 156

The k-tuple conjecture predicts infinitely many occurrences but finding one is infeasible

http://www.primepuzzles.net/puzzles/puzz_681.htm

Как я поняла, Jens K Andersen не нашёл решение для приведённого паттерна даже в случае не последовательных простых чисел.
Это один из паттернов для квадрата Стенли 5-го порядка из различных простых чисел с минимально возможной разностью между наибольшим и наименьшим числами набора (она равна 156). Выше приведено решение с разностью 180.

P.S. Кстати, на сайте в фрагментах строк
70 84 100 114
112 126 142 156
я вижу наличие ссылок, но у меня эти ссылки не работают. Интересно, что там?

-- Вт сен 09, 2014 12:33:22 --

По поводу последней задачи привожу результаты Pavlovsky:

Pavlovsky в сообщении #343577 писал(а):

Ниже представлены пандиагональные МК 5х5 с магической суммой в диапозоне [395,481]. Для всех нечетных магических сумм больше 481 можно построить пандиагональные МК 5х5. Правда это строго не доказано.

(Оффтоп)

395 = 5 7 11 13 17 23 31 37 41 43 53 67 71 73 83 97 101 103 113 127 131 137 167 197 227 
403 = 7 13 17 19 23 29 31 37 41 43 47 53 61 67 73 103 113 127 137 139 149 157 163 173 193 
409 = 5 7 11 13 29 31 41 43 47 53 59 61 71 73 79 83 97 101 109 127 157 163 181 193 211 
413 = 5 11 23 29 31 37 41 47 53 59 67 71 73 79 83 89 97 109 113 131 139 149 157 173 199 
419 = 5 13 19 23 29 31 37 47 53 59 67 71 73 83 89 97 103 107 113 137 149 157 163 173 197 
425 = 5 7 11 13 17 23 41 43 53 61 67 71 73 83 97 101 103 113 127 131 137 157 167 197 227 
431 = 5 7 11 13 17 19 31 37 41 43 47 53 71 73 97 101 103 107 127 137 167 173 179 233 263 
433 = 11 13 17 19 31 37 41 43 53 59 61 67 73 83 97 107 109 127 137 139 149 157 163 179 193 
437 = 7 11 13 17 23 29 37 41 43 47 53 59 67 73 97 101 103 107 131 137 163 167 179 223 257 
441 = 5 11 23 29 31 37 41 47 53 59 67 71 83 89 97 101 107 113 131 137 149 157 167 173 227 
443 = 11 17 23 29 31 41 43 47 53 59 61 67 71 73 79 83 97 101 109 113 173 179 193 229 233 
447 = 5 11 23 29 37 41 43 47 53 59 71 73 83 89 101 103 107 113 131 137 149 163 167 173 227 
449 = 5 13 23 29 31 37 43 61 67 71 79 83 89 97 101 107 109 113 127 131 137 149 167 179 197 
451 = 7 13 17 31 37 41 43 47 61 71 73 79 83 97 103 107 109 113 127 137 157 163 167 181 191 
457 = 7 13 17 19 23 29 31 37 41 43 47 53 61 67 73 139 149 157 163 167 173 181 191 193 211 
461 = 5 11 17 23 29 37 41 43 47 59 61 71 79 83 103 107 113 131 149 157 163 173 181 199 223 
463 = 13 19 31 37 41 43 47 53 59 61 67 71 73 83 97 109 127 137 139 149 157 163 167 179 193 
467 = 13 23 31 37 41 43 47 53 61 71 79 83 97 101 103 107 109 113 127 131 149 167 173 179 197 
469 = 7 11 13 17 23 29 37 41 43 47 53 59 73 79 97 101 103 109 113 163 193 199 223 229 283 
473 = 5 11 17 23 31 41 43 47 53 59 61 67 73 79 97 101 109 113 137 149 173 179 199 229 269 
475 = 11 23 31 41 43 53 59 61 67 71 73 79 83 89 97 101 103 109 131 139 151 163 181 193 223 
479 = 11 17 23 29 31 37 41 47 53 59 61 67 73 79 101 103 107 109 131 137 179 191 199 241 269 
481 = 11 17 23 29 31 41 43 47 53 59 61 67 73 79 83 89 97 103 109 139 199 211 229 241 271 
483 = 5 11 23 29 41 47 53 59 71 73 79 83 89 101 107 109 113 131 137 139 149 167 173 199 227 
485 = 5 19 31 41 47 53 59 61 67 73 79 83 89 101 107 113 127 137 139 149 151 163 167 173 191 
487 = 11 17 23 29 31 41 43 47 53 59 61 67 73 79 97 107 109 113 127 163 181 193 211 223 277 
491 = 11 17 23 29 31 41 43 47 53 59 61 71 73 83 97 101 109 113 127 139 191 197 211 251 277 
493 = 13 19 23 29 31 37 41 43 47 53 61 71 73 79 103 139 149 157 163 167 173 181 191 199 223 
497 = 11 17 23 29 31 41 43 47 61 67 71 79 83 97 101 107 113 127 163 167 173 179 193 229 233 
499 = 7 17 29 31 37 41 43 47 53 59 67 73 79 103 109 127 137 149 157 163 167 179 193 199 229 
503 = 11 17 23 29 31 41 43 47 61 67 79 83 89 97 103 107 113 127 139 163 167 179 197 239 263 
505 = 5 11 13 19 29 37 47 53 59 67 71 73 79 97 101 127 131 139 157 163 173 181 199 211 283 
509 = 11 13 17 19 23 29 31 37 41 43 53 61 101 107 131 137 139 149 157 179 181 191 199 227 269 
511 = 13 19 31 37 41 43 47 61 67 71 73 97 101 107 109 127 131 137 139 157 163 167 193 197 227 
515 = 5 7 11 13 17 19 31 37 41 43 47 53 71 73 97 101 103 107 127 137 251 257 263 317 347 
517 = 11 13 17 19 23 29 37 43 71 73 83 97 101 103 113 127 137 139 149 151 157 163 211 241 277 
521 = 11 13 17 19 29 31 53 59 61 67 71 79 83 89 101 107 109 149 157 179 191 193 233 241 263 
523 = 11 23 31 41 43 53 59 61 67 71 73 79 83 89 97 101 103 109 131 139 199 211 229 241 271 
527 = 11 17 23 29 31 41 43 47 53 59 61 67 71 73 79 83 97 101 109 113 257 263 277 313 317 
529 = 11 13 17 19 23 29 31 37 59 61 71 79 103 109 137 139 149 151 157 179 181 191 199 229 271 
531 = 11 17 23 29 31 41 43 47 53 59 61 71 73 83 101 113 137 149 167 179 191 197 211 251 317 
533 = 11 13 17 19 23 29 37 43 71 73 83 97 101 103 113 127 137 139 149 163 167 173 227 257 293 
535 = 5 7 11 13 17 19 31 37 41 43 47 53 61 67 73 101 103 127 137 157 281 283 307 317 337 
537 = 5 11 23 29 37 41 43 47 53 59 71 73 83 89 103 113 131 149 163 173 191 197 227 257 317 
539 = 23 29 31 37 47 53 59 67 73 79 83 89 97 109 113 131 137 139 149 157 167 173 197 199 257 
541 = 11 13 23 37 41 43 53 67 71 73 83 97 101 103 113 127 137 139 149 151 163 181 211 241 277 
545 = 11 17 23 29 31 41 43 47 53 59 61 71 73 83 101 113 151 163 181 191 193 197 211 251 331 
547 = 11 13 17 19 31 37 41 43 53 59 61 83 97 103 127 137 139 157 179 191 193 211 223 233 277 
549 = 11 13 17 19 23 29 41 47 53 59 71 73 83 101 113 137 139 149 167 179 227 229 239 257 269 
551 = 11 13 17 19 23 29 41 43 53 71 73 83 101 103 113 151 157 167 173 181 197 211 227 241 257 
553 = 11 17 23 29 31 41 43 47 61 67 79 83 89 97 103 139 151 163 173 179 181 193 223 229 313 
555 = 5 11 13 17 19 23 29 37 41 59 67 71 83 89 101 107 109 113 137 179 257 263 281 311 353 
557 = 11 13 17 19 23 29 37 43 47 53 71 73 83 97 101 103 107 113 127 137 281 283 293 307 317 
559 = 13 19 23 29 31 37 43 53 61 73 79 103 107 113 137 139 149 157 163 173 181 199 223 233 257 
561 = 11 13 17 19 23 29 41 47 53 59 71 73 83 101 113 137 139 149 167 179 239 241 251 269 281 
563 = 11 13 17 19 41 43 53 59 71 73 83 97 103 113 127 137 139 157 167 173 179 197 223 227 293 
565 = 11 17 23 29 31 41 43 47 53 59 61 73 83 89 103 151 163 181 193 199 211 223 229 241 271 
567 = 5 11 17 23 37 41 43 47 53 59 71 73 79 83 103 131 137 167 173 197 227 233 263 269 293 
569 = 11 13 17 19 41 43 53 59 67 73 83 97 107 109 137 139 149 163 167 173 179 193 197 263 293 
571 = 11 13 19 29 31 37 59 61 67 71 73 79 89 101 103 107 109 137 149 179 223 241 271 283 313 
573 = 11 17 23 29 31 41 43 47 53 59 61 71 73 83 101 113 131 137 151 191 239 251 269 281 359 
575 = 11 17 23 29 31 41 43 47 61 67 71 79 83 97 101 107 113 127 163 167 251 257 271 307 311 
577 = 11 17 23 29 37 41 43 53 67 73 79 101 103 113 127 151 157 163 167 179 181 193 229 241 307 
581 = 11 13 17 19 23 29 41 47 59 61 71 89 101 103 113 131 137 139 149 167 223 229 271 313 349 

Решение с разность между минимальным и максимальным числом равной 180 здесь есть:

463 = 13 19 31 37 41 43 47 53 59 61 67 71 73 83 97 109 127 137 139 149 157 163 167 179 193

С разностью 156 я не нашла.
Но пандиагональных квадратов 5-го порядка из не последовательных простых чисел море. И строить их просто. А каждому такому квадрату соответствует свой квадрат Стенли (один и только один).

[Nataly-Mak]

Нашла в старых файлах свои пандиагональные квадраты 5-го порядка из простых чисел. Добавлю их к результатам Pavlovsky, хотя разности 156 у меня тоже нет, все разности больши-и-и-е:

(Оффтоп)

3  271  193  31  109 
157  13  107  233  97 
337  59  61  139  11 
43  137  241  163  23 
67  127  5  41  367 
S= 607

5  131  379  23  73 
359  13  71  107  61 
173  37  41  349  11 
31  347  113  103  17 
43  83  7  29  449 
S= 611

3  373  163  31  43 
127  13  41  359  73 
397  59  37  109  11 
19  107  367  97  23 
67  61  5  17  463 
S= 613

3  103  337  37  139 
307  13  137  89  73 
223  59  43  283  11 
19  281  97  193  29 
67  163  5  17  367 
S= 619

3  127  337  31  139 
331  13  137  89  67 
223  29  61  313  11 
43  311  97  163  23 
37  157  5  41  397 
S= 637

3  103  397  31  109 
367  13  107  89  67 
193  53  37  349  11 
19  347  97  157  23 
61  127  5  17  433 
S= 643

5  181  379  23  73 
359  13  71  157  61 
223  37  41  349  11 
31  347  163  103  17 
43  83  7  29  499 
S= 661

5  191  379  23  73 
359  13  71  167  61 
233  37  41  349  11 
31  347  173  103  17 
43  83  7  29  509 
S= 671

5  331  271  23  73 
251  13  71  307  61 
373  37  41  241  11 
31  239  313  103  17 
43  83  7  29  541 
S= 703

5  397  211  23  73 
191  13  71  373  61 
439  37  41  181  11 
31  179  379  103  17 
43  83  7  29  547 
S= 709

5  191  463  23  73 
443  13  71  167  61 
233  37  41  433  11 
31  431  173  103  17 
43  83  7  29  593 
S= 755

5  197  463  23  73 
443  13  71  173  61 
239  37  41  433  11 
31  431  179  103  17 
43  83  7  29  599 
S= 761

5  107  463  23  181 
443  13  179  83  61 
257  37  41  433  11 
31  431  89  211  17 
43  191  7  29  509 
S= 779

5  251  463  23  73 
443  13  71  227  61 
293  37  41  433  11 
31  431  233  103  17 
43  83  7  29  653 
S= 815

3  103  571  31  109 
541  13  107  89  67 
193  53  37  523  11 
19  521  97  157  23 
61  127  5  17  607 
S= 817

3  283  397  31  109 
367  13  107  269  67 
373  53  37  349  11 
19  347  277  157  23 
61  127  5  17  613 
S= 823

5  97  463  23  241 
443  13  239  73  61 
307  37  41  433  11 
31  431  79  271  17 
43  251  7  29  499 
S= 829

5  107  463  23  241 
443  13  239  83  61 
317  37  41  433  11 
31  431  89  271  17 
43  251  7  29  509 
S= 839

5  191  389  23  241 
359  13  239  167  71 
401  47  41  349  11 
31  347  173  281  17 
53  251  7  29  509 
S= 849

5  263  379  23  181 
293  13  179  227  139 
401  103  53  283  11 
43  281  233  277  17 
109  191  7  41  503 
S= 851

5  379  359  37  73 
163  13  71  367  239 
433  227  43  139  11 
19  137  373  293  31 
233  97  7  17  499 
S= 853

3  103  577  31  139 
541  13  137  89  73 
223  59  37  523  11 
19  521  97  193  23 
67  157  5  17  607 
S= 853

[Dmitriy40]

Alexu007 в сообщении #905748 писал(а):

2 млрд за 4 секунды на обычном компьютере (у меня шустрый ноутбук) - это реально? Пустой цикл из 2-х миллиардов, который ничего не делает - дольше выполняться будет...

Я Вам уже отвечал ведь - post905128.html#p905128
И цикл разумеется выполняется не 2млрд, а (для 387-го миллиарда) примерно 50 тысяч раз (обрабатывая при этом все числа в диапазоне 2млрд) плюс 75млн чисел находит (т.е. второй цикл копирования 75млн чисел). И вот это выполнить за 4с вполне реально как показывает практика.

[Nataly-Mak]

Ну что же, пожалуй, я покажу алгоритм проверки построения квадрата Стенли 5-го порядка, как я поняла его в изложении whitefox.
Сразу замечу, что мой алгоритм (изложенный выше) несколько отличается от алгоритма whitefox.
Схему квадрата Стенли обозначим так:

a11 a12 a13 a14 a15
a21 a22 a23 a24 a25
a31 a32 a33 a34 a35 
a41 a42 a43 a44 a45
a51 a52 a53 a54 a55

Набор из 25 чисел я выбрала такой, из чисел которого квадрат составляется:

0, 2, 6, 8, 12, 18, 26, 32, 36, 38, 48, 62, 66, 68, 78, 92, 96, 98, 108, 122, 126, 132, 162, 192, 222

Требования к набору:
1. нормализация;
2. упорядоченность (числа расположены строго по возрастанию).
Ну и разумеется, набор должен удовлетворять необходимому условию: сумма всех чисел набора кратна 5. Иначе набор и проверять не имеет смысла.

Итак, начинаем: сразу же выполняем следующие присвоения:

a11=0, a55=222

Далее начинаем перебор 4-х элементов квадрата: a12, a13, a14, a15, при этом перебирать их надо так: $a_{12}<a_{13}<a_{14}<a_{15}$ (основываясь на свойствах квадрата Стенли).
Первая подходящая комбинация будет такой, при которой сложится последняя строка квадрата, так как все элементы этой строки сразу же вычисляются при задании элементов a12, a13, a14, a15.
Вот, например, такая подходящая комбинация для этих четырёх перебираемых элементов:

a11=6
a12=36
a13=66
a14=96 

Тогда квадрат принимает вид (с полными первой и пятой строками):

0 6 36 66 96
x x x x x
x x x x x
x x x x x
126 132 162 192 222

Теперь выбрасываем из набора использованные элементы, оставшийся набор:

2, 8, 12, 18, 26, 32, 38, 48, 62, 68, 78, 92, 98, 108, 122

Опять же основываясь на свойствах квадрата Стенли, элементу a21 мы даём только одно значение - минимальное в оставшемся наборе. То есть этот элемент (как и следующие - a31 и a41) уже и не перебирается.
Итак, присваиваем: $a_{12}=2$.
Сразу вычисляем элементы второй строки. Если каждый из них принадлежит оставшемуся набору, всё хорошо - можно идти дальше. В противном случае - возврат на поиск другой подходящей комбинации элементов a12, a13, a14, a15.
[Внимание! Вот здесь и видим действие "перебора с возвратом".]

В данном примере имеем полностью хорошую вторую строку:

0 6 36 66 96
2 8 38 68 98
x x x x x
x x x x x
126 132 162 192 222

Ну, и думаю, не надо показывать, как проверить построение оставшихся двух строк квадрата - надо повторить все действия, которые выполнялись при заполнении второй строки.
Окончательное решение:

0 6 36 66 96
2 8 38 68 98
12 18 48 78 108
26 32 62 92 122
126 132 162 192 222
S=370

Таким образом, в алгоритме whitefox фактически 4 свободных переменных!
Если есть вопросы по описанию алгоритма, пожалуйста, задавайте. На что смогу, отвечу.

В примере использован наименьший квадрат Стенли 5-го порядка из не последовательных простых чисел Pavlovsky.

[Nataly-Mak]

Nataly-Mak в сообщении #906206 писал(а):

Итак, присваиваем: $a_{12}=2$.

Прошу прощения, здесь, конечно, опечатка. Должно быть:
Итак, присваиваем: $a_{21}=2$.

[Nataly-Mak]

Безобразие, ещё опечатка

Цитата:

Вот, например, такая подходящая комбинация для этих четырёх перебираемых элементов:

a11=6
a12=36
a13=66
a14=96 

Правильно так:
Вот, например, такая подходящая комбинация для этих четырёх перебираемых элементов:

a12=6
a13=36
a14=66
a15=96 

Ещё раз прошу прощения.

[Alexu007]

Dmitriy40 в сообщении #905823 писал(а):

И цикл разумеется выполняется не 2млрд, а (для 387-го миллиарда) примерно 50 тысяч раз (обрабатывая при этом все числа в диапазоне 2млрд) плюс 75млн чисел находит (т.е. второй цикл копирования 75млн чисел). И вот это выполнить за 4с вполне реально как показывает практика.

За 10 сек выполняется поиск простых чисел до первого миллиарда (50 847 534 штук) у меня пока. Продолжаю работу по ускорению, но это имеет мало смысла, потому что:

А как вы всё таки ищете простые числа с произвольного числа? Вы объясняли, но я ничего не понял. Сам принцип решета Эрастофена в том, что его всегда с начала заполнять надо... или я чего то не понимаю.

[Dmitriy40]

Alexu007 в сообщении #906560 писал(а):

А как вы всё таки ищете простые числа с произвольного числа? Вы объясняли, но я ничего не понял. Сам принцип решета Эрастофена в том, что его всегда с начала заполнять надо...

Я бы сказал не совсем в этом принцип, а скорее в вычёркивании всех чисел кратных известным простых числам из непрерывного массива всех чисел и в результате в массиве остаются лишь новые простые числа.
Начинать с произвольного числа можно вот почему: чтобы вычеркнуть из массива заданной длины, начинающегося с произвольного числа, все составные числа (кратные простым) достаточно иметь список всех простых чисел величиной до квадратного корня из точки конца массива. Поэтому решето модифицируем, вместо постепенного поиска простых и добавлении их к списку известных, сразу находим (ну или читаем из файла, уж как удобнее, вычислить раз в 10 быстрее) все простые числа не превосходящие \sqrt{N+size} (конец вычисляемого массива). Потом циклом по этому списку определяем смещение в массиве первого числа, кратного данному простому (остаток от деления величины начала массива на данное простое число) и начиная с него идём по массиву и вычёркиваем кратные ему числа, ну как обычно в решете. После обработки всего списка простых все составные числа в массиве вычеркнутся.
Сама идея - правильно найти это вот смещение первого кратного числа в массиве. Делается примерно так:

Используется синтаксис C

offset = N mod p[i];//N - начальное число, p[i] - простое, offset - смещение в массиве кратного ему
if (offset != 0) offset = p[i] - offset;

Вот начиная с найденного offset и вычеркиваем дальше кратные числа.

[Nataly-Mak]

Наконец, все всё поняли
Итак, на чём мы остановились? По алгоритму поиска квадрата Стенли 5-го порядка вопросов, кажется, ни у кого нет. Это хорошо.

Вот Progger и whitefox пропали - это плохо

Я пока занялась пандиагональными квадратами 8-го порядка из простых чисел (последовательных и не последовательных).

Крутить программу whitefox пока бросила. Мне нужен вывод решений с "дырками". Без этой информации крутить программу вслепую, не зная, что там вообще находится, как-то очень скучно.
А вывод решений с "дырками" сделать некому.

[Progger]

Я не совсем пропал . Для квадратов 4-го и 5-го порядка дошёл до $10^{15}$. Ни квадрата 5-го порядка, ни нового ассоциативного квадрата 4-го порядка там нет. Про пандиагональный квадрат 8-го порядка тему видел, но пока не придумал, как реализовать поиск с приемлемой скоростью.