Переборная задача, есть ли шанс?

[Nataly-Mak]

Ещё одна аналогичная задача. Теперь цель – построить идеальный квадрат 9-го порядка из простых чисел.
Такой квадрат можно построить:
1) из арифметической прогрессии длины 81 из простых чисел;
но такую прогрессию ещё пока не нашли, хотя доказано, что она существует;
2) из простых чисел, образующих 9 арифметических прогрессий длины 9 с одинаковой (любой!) разностью, первые члены которых образуют арифметическую прогрессию;
такие прогрессии найти тоже очень непросто;
3) наконец, из простых чисел, образующих 9 арифметических прогрессий длины 9 с одинаковой (любой!) разностью, таких, что из первых членов этих прогрессий можно составить магический квадрат 3-го порядка.

Вот третий вид прогрессий, по-моему, самый подходящий для поиска.
Возможны два пути.

а) ищем $N$ (не менее 9) арифметических прогрессий из простых чисел с одинаковой разностью, а затем проверяем, можно ли из первых членов найденных прогрессий составить магический квадрат 3-го порядка. Если это удаётся, задача решена.

Кстати, для построения пандиагонального квадрата 9-го порядка alexBlack нашёл 223 последовательности нужного вида. И среди первых членов этих последовательностей нашлись только две девятки, удовлетворяющие нужному условию. Эти две девятки и дали два пандиагональных квадрата.

б) берём сразу набор из 9 простых чисел, составляющих магический квадрат 3-го порядка, например:

17, 89, 71, 113, 59, 5, 47, 29, 101

Начинаем от этих первых членов строить арифметические прогрессии с одинаковой разностью, следя за тем, чтобы все получающиеся числа были простые и различные. Если удастся получить 8 новых строк, задача решена. Понятно, что можно пробовать варианты с разными разностями прогрессий. Кроме того, можно брать различные исходные наборы, ведь квадратов 3-го порядка из простых чисел можно очень много построить. Вот, например, ещё один набор:

47, 191, 173, 263, 137, 11, 101, 83, 227

Предлагаю всем попробовать решить эту задачу. Конечно, должна предупредить: прогрессии не найдутся сразу. Задача для настойчивых

В теме «Магические квадраты» я выложила свою программу построения идеального квадрата 9-го порядка, реализующую другой разработанный мной алгоритм. Желающие могут её испытать и проверить ряд потенциальных массивов простых чисел.

[Nataly-Mak]

Попробовала сама поиск прогрессий. В программе задействован массив из 100.000 первых простых чисел.
Это 5 прогрессий с разностью 210:

199  409  619  829  1039  1249  1459  1669  1879 
 3499  3709  3919  4129  4339  4549  4759  4969  5179 
 10859  11069  11279  11489  11699  11909  12119  12329  12539 
 564973  565183  565393  565603  565813  566023  566233  566443  566653 
 1288607  1288817  1289027  1289237  1289447  1289657  1289867  1290077  1290287

Это 5 прогрессий с разностью 840:

6043  6883  7723  8563  9403  10243  11083  11923  12763 
 10861  11701  12541  13381  14221  15061  15901  16741  17581 
 103837  104677  105517  106357  107197  108037  108877  109717  110557 
 201781  202621  203461  204301  205141  205981  206821  207661  208501 
 915611  916451  917291  918131  918971  919811  920651  921491  922331

Не густо

[Nataly-Mak]

Прогрессии отменяются

Оказывается, не только в первой строке примитивного квадрата должны быть элементы, из которых можно составить магический квадрат 3-го порядка, но и в первом столбце тоже!
Осенило и попробовала. Итак, берём любой набор из 9 простых чисел, которые составляют магический квадрат 3-го порядка, например:

5, 17, 29, 47, 59, 71, 89, 101, 113

Далее строим $N$ (не менее 9) подобных последовательностей, то есть с такими же разностями между соседними членами. Конечно, все они должны состоять из простых и различных чисел. Построили много, например, 100 штук таких последовательностей.
Теперь проверяем, есть ли среди первых членов этих последовательностей такие 9, из которых можно составить магический квадрат 3-го порядка. Если нашлись такие 9 первых членов, задача решена.
Приведу пример таких 9 последовательностей, но из произвольных натуральных чисел:

5 17 29 47 59 71 89 101 113
4 16 28 46 58 70 88 100 112
6 18 30 48 60 72 90 102 114
9 21 33 51 63 75 93 105 117
8 20 32 50 62 74 92 104 116
7 19 31 49 61 73 91 103 115
10 22 34 52 64 76 94 106 118
12 24 36 54 66 78 96 108 120
11 23 35 53 65 77 95 107 119

Первые члены последовательностей здесь: 5, 4, 6, 9, 8, 7, 10, 12, 11. Из них можно составить магический квадрат 3-го порядка.
Это готовый примитивный квадрат, из которого с помощью матричного преобразования получаем идеальный квадрат.

Впрочем, 9 элементов, из которых можно составить магический квадрат 3-го порядка, всегда образуют три арифметических прогрессии с одинаковой разностью, первые члены которых образуют арифметическую прогрессию. Но всё равно это условие слабее, чем сплошные прогрессии длины 9.
Итак, решаем задачу по-другому. Конечно, если кому-то удастся решить с прогрессиями, тоже будет здорово.

-- Ср мар 16, 2011 17:07:25 --

Только сейчас заметила, что у меня в первом столбце элементы образуют арифметическую прогрессию длины 9 (а не три отдельных прогрессии), не совсем удачный взяла пример. Сейчас попробую другой вариант с той же исходной последовательностью.

[Nataly-Mak]

Пример с другими последовательностями (исходная та же, просто она на другом месте стоит, последовательности можно переставлять как угодно, примитивный квадрат должен получиться симметрическим):

18 30 42 60 72 84 102 114 126
10 22 34 52 64 76 94 106 118
11 23 35 53 65 77 95 107 119
21 33 45 63 75 87 105 117 129
13 25 37 55 67 79 97 109 121
5 17 29 47 59 71 89 101 113
15 27 39 57 69 81 99 111 123
16 28 40 58 70 82 100 112 124
8 20 32 50 62 74 92 104 116

Из первых элементов последовательностей составляется такой магический квадрат 3-го порядка:

18 5 16
11 13 15
10 21 8

Моё матричное преобразование превращает данный примитивный квадрат в идеальный квадрат 9-го порядка:

23 74 72 57 106 29 121 21 100
101 37 129 16 95 20 84 69 52
92 30 81 64 47 109 45 124 11
55 117 40 119 8 102 27 76 59
18 99 22 71 67 63 112 35 116
75 58 107 32 126 15 94 17 79
123 10 89 25 87 70 53 104 42
82 65 50 114 39 118 5 97 33
34 113 13 105 28 77 62 60 111

Осталось всё это проделать так, чтобы все числа в примитивном квадрате получились простые и различные.

Кто смелый и умелый?

[Nataly-Mak]

Уважаемые форумчане, помогите с комбинаторной задачкой.
Что-то я растерялась, вроде задачка несложная...

Имеем массив из 36 попарно различных чисел:

1  3  5  7  11  13  17  19  23  29  31  37  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  151  157  163 

Сумма всех чисел массива равна 2556. Это "правильный" массив, то есть такой, какой нам нужен.
Теперь добавляем к массиву два новых числа: 41 и 149.
Требуется определить, сколько "правильных" массивов (из 36 попарно различных чисел с суммой всех чисел равной 2556) можно получить из нового набора, состоящего из 38 чисел.
У меня есть программа для формирования массивов, но она работает по такому принципу: фиксируем несколько первых чисел массива, остальные ищем из всех оставшихся чисел набора.
В этом примере я зафиксировала первые 24 числа исходного массива, остальные 12 чисел ищу из оставшихся 14 чисел.
Программа в этом случае выдаёт единственный "правильный" массив из 36 чисел - исходный массив! То есть числа 41 и 149 она никак в массив не вставляет.
Но правильно ли это
Мне кажется, что надо как-то по-другому решать. У меня не полный перебор всех вариантов.
Подскажите, пожалуйста.

Если зафиксировать только одно число массива - 1, а остальные 35 чисел искать из оставшихся 37, это, наверное, не выполнится сто лет
Но именно так можно сделать полный перебор всех вариантов. Есть ли другой путь?

P.S. Забыла сказать: число 1 должно присутствовать в "правильном" массиве обязательно.

-- Ср июн 12, 2013 07:45:01 --

Попробовала вариант 23 фиксированных числа и 13 варьируются. Выполнилось мгновенно, результат тот же - один "правильный" массив.
Может быть, и вариант 1+35 выполнится быстро?
Что скажете, коллеги?

-- Ср июн 12, 2013 08:03:06 --

Ура, нашла один "правильный" массив, содержащий числа 41 и 149, использовав нехитрый приём:

1  3  5  7  11  13  17  19  23  29  31  37  41  47  53  59  61  67  71  73  79  83  149  97  43  103  107  109  113  127  131  137  139  151  157  163

Значит, моё предположение верно: таких массивов будет несколько.
Надо найти их все
Как это можно сделать кроме полного тупого перебора (вариант 1+35)?

[Nataly-Mak]

Вот что "наработала"

(Оффтоп)

ИСХОДНЫЙ ПРАВИЛЬНЫЙ МАССИВ:

1 3 5 7 11 13 17 19 23 29 31 37 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137
139 151 157 163


НАЧАЛО МАССИВА (ВАРИАНТ 22+14):

1 3 5 7 11 13 17 19 23 29 31 37 43 47 53 59 61 67 71 73 79 83

S1=832, s2=2556-832=1724

89 97 101 103 107 109 113 127 131 137 139 151 157 163
97 103 107 109 113 127 131 137 139 151 157 163 41 149

KOLICHESTVO MASSIVOV 2

*****

НАЧАЛО МАССИВА (ВАРИАНТ 21+15):

1 3 5 7 11 13 17 19 23 29 31 37 43 47 53 59 61 67 71 73 79

S1=749, S2=2556-749=1807

83 89 97 101 103 107 109 113 127 131 137 139 151 157 163
83 97 103 107 109 113 127 131 137 139 151 157 163 41 149
89 97 101 103 109 113 127 131 137 139 151 157 163 41 149

KOLICHESTVO MASSIVOV 3

*****

НАЧАЛО МАССИВА (ВАРИАНТ 20+16):

1 3 5 7 11 13 17 19 23 29 31 37 43 47 53 59 61 67 71 73

S1=670, S2=2556-670=1886

79 83 89 97 101 103 107 109 113 127 131 137 139 151 157 163
79 83 97 103 107 109 113 127 131 137 139 151 157 163 41 149
79 89 97 101 103 109 113 127 131 137 139 151 157 163 41 149

KOLICHESTVO MASSIVOV 3

*****

НАЧАЛО МАССИВА (ВАРИАНТ 19+17):

1 3 5 7 11 13 17 19 23 29 31 37 43 47 53 59 61 67 71

S1=597, S2=2556-597=1959

73 79 83 89 97 101 103 107 109 113 127 131 137 139 151 157 163
73 79 83 97 103 107 109 113 127 131 137 139 151 157 163 41 149
73 79 89 97 101 103 109 113 127 131 137 139 151 157 163 41 149

KOLICHESTVO MASSIVOV 3

*****

НАЧАЛО МАССИВА (ВАРИАНТ 18+18):

1 3 5 7 11 13 17 19 23 29 31 37 43 47 53 59 61 67

S1=526, S2=2556-526=2030

71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 151 157 163
71 73 79 83 97 103 107 109 113 127 131 137 139 151 157 163 41 149
71 73 79 89 97 101 103 109 113 127 131 137 139 151 157 163 41 149

KOLICHESTVO MASSIVOV 3


*****

НАЧАЛО МАССИВА (ВАРИАНТ 17+19)

1 3 5 7 11 13 17 19 23 29 31 37 43 47 53 59 61

S1=459, S2=2556-459=2097

67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 151 157 163
67 71 73 79 83 97 103 107 109 113 127 131 137 139 151 157 163 41 149
67 71 73 79 89 97 101 103 109 113 127 131 137 139 151 157 163 41 149

KOLICHESTVO MASSIVOV 3


*****

НАЧАЛО МАССИВА (ВАРИАНТ 16+20)

1 3 5 7 11 13 17 19 23 29 31 37 43 47 53 59

S1=398, S2=2556-398=2158

61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 151 157 163
61 67 71 73 79 83 97 103 107 109 113 127 131 137 139 151 157 163 41 149
61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 151 157 163 41 149

KOLICHESTVO MASSIVOV 3

*****

НАЧАЛО МАССИВА (ВАРИАНТ 15+21)

1 3 5 7 11 13 17 19 23 29 31 37 43 47 53

S1=339, S2=2556-339=2217

59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 151 157 163
59 61 67 71 73 79 83 97 103 107 109 113 127 131 137 139 151 157 163 41 149
59 61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 151 157 163 41 149
61 67 71 73 79 83 89 97 101 103 107 109 113 127 137 139 151 157 163 41 149

KOLICHESTVO MASSIVOV 4

В последнем варианте зафиксировано 15 первых чисел массива, остальные 21 варьируются.
Уже найдено 4 нужных массива (программа выводит варьируемых числа массива - "хвост", начало во всех массивах одинаково).
S1 - сумма зафиксированных чисел массива, S2 - сумма варьируемых чисел, 2556 - сумма всех чисел массива.
Вопреки ожиданиям программа пока выполняется несколько секунд.

Скажите хотя бы: я на правильном пути?

-- Ср июн 12, 2013 12:01:18 --

5 массивов появилось на этом шаге:

НАЧАЛО МАССИВА (ВАРИАНТ 14+22)

1  3  5  7  11  13  17  19  23  29  31  37  43  47

S1=286, S2=2556-286=2270

 53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  151  157  163 
 53  59  61  67  71  73  79  83  97  103  107  109  113  127  131  137  139  151  157  163  41  149 
 53  59  61  67  71  73  79  89  97  101  103  109  113  127  131  137  139  151  157  163  41  149 
 53  61  67  71  73  79  83  89  97  101  103  107  109  113  127  137  139  151  157  163  41  149 
 59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  139  151  157  163  41  149 
KOLICHESTVO MASSIVOV 5 

Больше пока не появляются новые массивы, дошла уже до варианта:

НАЧАЛО МАССИВА (ВАРИАНТ 5+31)

1  3  5  7  11

S1=27, S2=2556-27=2529

 13  17  19  23  29  31  37  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  151  157  163 
 13  17  19  23  29  31  37  43  47  53  59  61  67  71  73  79  83  97  103  107  109  113  127  131  137  139  151  157  163  41  149 
 13  17  19  23  29  31  37  43  47  53  59  61  67  71  73  79  89  97  101  103  109  113  127  131  137  139  151  157  163  41  149 
 13  17  19  23  29  31  37  43  47  53  61  67  71  73  79  83  89  97  101  103  107  109  113  127  137  139  151  157  163  41  149 
 13  17  19  23  29  31  37  43  47  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  139  151  157  163  41  149 
KOLICHESTVO MASSIVOV 5

До конца осталось совсем немного. Однако программа уже начала задумываться
Это полный тупой перебор. Другого пути не вижу для решения задачи.

[venco]

Если я правильно понял, то из массива с 38-ю числами надо выкинуть два числа с определённой суммой (190). Это просто: сортируете массив, и двумя указателями бежите с начала и конца. Если сумма указываемых чисел равна 190, их можно выкинуть. Если сумма больше 190, сдвигаете верхний указатель на один к центру, если меньше, то сдвигате нижний. Когда указатели сойдутся, все варианты перебраны. Можно даже пальцами перебрать: 41+149, 51+139, 59+131, 83+107, 89+101.

[iifat]

svv в сообщении #421423 писал(а):

Увеличиваем N[k] на единицу. Если получилось 3 -- выводим на печать

Даже если сумма встретилась три раза, это не значит, что тройки не пересекаются. Отдельную проверку надо.

[Nataly-Mak]

venco в сообщении #735849 писал(а):

Если я правильно понял, то из массива с 38-ю числами надо выкинуть два числа с определённой суммой (190). Это просто: сортируете массив, и двумя указателями бежите с начала и конца. Если сумма указываемых чисел равна 190, их можно выкинуть. Если сумма больше 190, сдвигаете верхний указатель на один к центру, если меньше, то сдвигате нижний. Когда указатели сойдутся, все варианты перебраны. Можно даже пальцами перебрать: 41+149, 51+139, 59+131, 83+107, 89+101.

Эх... действительно просто. Спасибо.
Однако на пальцах-то поняла...
Берём ранжированный массив:

1   3    5   7  11  13   17  19   23   29    31   37  41   43   47   53   59   61    67
71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  149  151  157  163

начинаем перебор с числа 3 (так как число 1 выбрасывать нельзя в любом случае), ищем число, которое даёт 190 в сумме с числом 3, нет такого числа; дальше проверяем число 5 и т. д. до конца массива.
А вот как программно реализовать указанную вами процедуру с двумя указателями, не соображу.
Понимаю так: по одной переменной перебор идёт с начала массива (первый указатель), а по другой - с "хвоста" (второй указатель). Правильно?
Как сдвигать указатели влево-вправо к центру массива (ну, или по-вашему - вверх-вниз)?

Далее у меня сейчас посложнее задача: общий массив состоит из 44 чисел, надо выбрать все "правильные" массивы из 36 чисел. То есть здесь надо выбросить 8 чисел с определённой суммой. Решаю тем же методом, какой показан для первой задачи.
А вашим методом здесь можно? Надо подумать...

Своим методом дошла до варианта:

Начало массива (вариант 6+30):

3  5  7  11  13  17

Сумма всех чисел в массиве равна 2628.
S1=56, S2=2628-56=2572

 19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  149  157  197 
 19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  149  163  191 
 19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  149  173  181 
 19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  151  173  179 
 19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  157  167  179 
 19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  163  167  173 
 19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  149  151  163  179 
 19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  149  157  163  173 
 19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  139  149  151  167  173 
 19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  131  137  139  149  151  157  173 
 19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  131  137  139  149  151  163  167 

KOLICHESTVO MASSIVOV 11 

Здесь число 3 всегда должно оставаться в массиве, остальные можно варьировать.
Понятно, что здесь дольше программа работает, так как чисел в массиве больше.

Общий массив в этой задаче - первые 44 нечётных простых числа

-- Ср июн 12, 2013 18:29:16 --

iifat
Задача с "тройками" давно решена
На дату посмотрите. Просто я не стала открывать новую тему, так как у меня опять переборная задача.

[venco]

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

Далее у меня сейчас посложнее задача: общий массив состоит из 44 чисел, надо выбрать все "правильные" массивы из 36 чисел. То есть здесь надо выбросить 8 чисел с определённой суммой. Решаю тем же методом, какой показан для первой задачи.
А вашим методом здесь можно?

Увы, нельзя. Можно попробовать модифицировать метод - собрать все возможные суммы из четырёх чисел - реально, хотя памяти потребуется много. Затем просканировать получившийся список аналогичным способом, проверяя возможные повторы чисел.

[Nataly-Mak]

Понятно.
Значит, мой метод пока единственно возможный для этой задачи.
Сейчас зафиксировала в массиве первые 5 чисел, вариант 5+31. Программа задумалась надолго
Может быть, ещё как-то можно решить - быстрее?

[venco]

См. выше.

[Nataly-Mak]

Я что-то пропустила?
Вы написали:

Цитата:

Увы, нельзя.

И далее:

Цитата:

Можно попробовать модифицировать метод - собрать все возможные суммы из четырёх чисел - реально, хотя памяти потребуется много. Затем просканировать получившийся список аналогичным способом, проверяя возможные повторы чисел.

Это будет быстрее?
Для меня это слишком сложно, я разучилась совсем работать со списками данных, забыла всё напрочь

[venco]

Это будет быстро, по моим прикидкам - меньше секунды.
Но если вы ещё столько-же чисел добавите - будет швах.

[Nataly-Mak]

Нет, ещё столько же добавлять не буду
Мне очень надо убедиться, что в приведённой задаче с массивом из 44 чисел можно выбрать только 11 "правильных" массивов.
Это, собственно, проверка результата, полученного давно maxal.

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

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

Вот первый потенциальный массив простых чисел:

3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 163 191

сумма всех чисел массива равна 2628. Массив даёт МК с магической константой 438.

Таких наборов несколько:

[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 157, 197]
[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 163, 191]
[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 173, 181]
[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 151, 173, 179]
[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 157, 167, 179]
[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 163, 167, 173]
[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 149, 151, 163, 179]
[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 149, 157, 163, 173]
[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 139, 149, 151, 167, 173]
[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 131, 137, 139, 149, 151, 157, 173]
[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 131, 137, 139, 149, 151, 163, 167]

Заодно интересно разобраться с алгоритмом решения подобных задач.