Комментарии 17
Очень сумбурно написано, побольше бы объяснений. А так читать интересно, спасибо
По идее, можно при помощи китайской теоремы об остатках быстро (?) искать простые числа.
Первое простое число - 2. Очевидно, все остальные простые числа сравнимы с единицей по модулю двух.
Второе простое число - 3. Все остальные простые числа по модулю 3 могут быть сравнимы лишь с 1 или с 2.
Система { x mod 2 = 1; x mod 3 = 1 } имеет решение x mod 6 = 1. Не подходит.
Система { x mod 2 = 1; x mod 3 = 2 } имеет решение x mod 6 = 5. То, что нужно. Добавляем x mod 5 = ... в систему уравнений.
С тремя уравнениями находим:
{ x mod 2 = 1; x mod 3 = 1; x mod 5 = 1 } --> x mod 30 = 1 (отбрасываем)
{ x mod 2 = 1; x mod 3 = 1; x mod 5 = 2 } --> x mod 30 = 7 (простое)
{ x mod 2 = 1; x mod 3 = 1; x mod 5 = 3 } --> x mod 30 = 13 (простое)
{ x mod 2 = 1; x mod 3 = 1; x mod 5 = 4 } --> x mod 30 = 19 (простое)
{ x mod 2 = 1; x mod 3 = 2; x mod 5 = 1 } --> x mod 30 = 11 (простое)
{ x mod 2 = 1; x mod 3 = 2; x mod 5 = 2 } --> x mod 30 = 17 (простое)
{ x mod 2 = 1; x mod 3 = 2; x mod 5 = 3 } --> x mod 30 = 23 (простое)
{ x mod 2 = 1; x mod 3 = 2; x mod 5 = 4 } --> x mod 30 = 29 (простое)
Т.е. множество известных простых чисел у нас разрастается очень быстро.
{ 2 },
{ 2, 3 },
{ 2, 3, 5 },
{ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 }
На следующей итерации мы найдём все простые числа, не превышающие 6469693230.
Ещё бы как-то соптимизировать перебор остатков, с которыми требуется решать систему... Хотя даже без оптимизаций он хорошо распараллеливается.
Что-то в этом роде:
import math
import operator
import itertools
def chrem_precalc(a):
M = math.prod(a)
def gen_factor(a_i):
M_i = M // a_i
M_i_inv = pow(M_i, -1, a_i)
return M_i * M_i_inv
return ([gen_factor(a_i) for a_i in a], M)
def chrem_solve(r, pre):
(f, M) = pre
return sum(map(operator.mul, r, f)) % M
def gen_all_r(a):
r_ranges = [range(1, a_i) for a_i in a]
return itertools.product(*r_ranges)
def moar_primes(known_primes):
pre = chrem_precalc(known_primes)
candidates = [chrem_solve(r, pre) for r in gen_all_r(known_primes)]
m = max(known_primes)
M = pre[1]
return known_primes + sorted(list(set([(x + M, x)[x > m] for x in candidates])))
moar_primes([2])
moar_primes([2, 3])
moar_primes([2, 3, 5])
moar_primes([2, 3, 5, 7])
Но всё же результаты надо дополнительно просеивать, т.к. длина результата при последовательном применении функции растет быстрее, чем квадратично.
Как известно, синус вычисляется через полиномиальный ряд. А что если взять ряд сумм синусов и каждый синус развернуть в полиномиальный ряд. Получится новый ряд, в котором возможно, получится сделать упрощения, а значит сэкономить на вычислениях.
Позвольте поинтересоваться, а какова постановка задачи и какой вывод? Какие преимущества у вашего подхода и с чем его вообще корректно сравнивать?
Ваши дроби получаются из суммы обратных первым n простым числам.
В числителе все слагаемые кроме одного делятся на p_1, все, кроме одного делятся на p_2 и т.д… Следовательно, числитель не делится на первые n простых.
Получилось обычное решето Эратосфена.
Вы открыли замечательный факт, что GCD(abс, x) = 1 для чисел, не делящехся на a, b, c.
При раскрытии через сумму вы получаете, что знаменатель — произведение всех ваших простых чисел, а в числителе отсаются взаимно простые.
Далее, с учетом, что любое составное число имеет делитель не превосходящий его корень, вы можете таким методом "найти" все простые до sqrt(abc). Так что, если в вашей таблице возьмете корнень из "максимальное", то у вас останутся только простые числа в этом интервале. А выше этого предела — уж как повезет. Там могут выпасть и простые числа, но в основном будут составные.
Ваш метод есть обобщение эвристики — перебирать в решете только нечетные числа. Или только числа вида 6k+1 и 6k+5.
И главное, этот ваш метод будет на порядки медленнее любого решета. Конечно, красиво, что есть уравнение для простых чисел. Но символьные вычисления над этой конструкцией уж очень неэффективны.
Извините, но судя по КДПВ, 5 не является простым числом. Мы что-то не знаем?
Когда-то очень интересовался этой задачей и разгадкой. Дошел до того, что попробовал установить последовательность непростых чисел, тех которые имеют одинаковую структуру с простыми (6х+-1). Она, получается, есть, но одной формулой никак не выводилась, потому что непонятно на каждом отрезке, какое количество будет 5 и 7 (5х+7у)
Он пытается преобразовать произведение в сумму!
А простые находятся в экстремумах функции (судя по графику)? А нельзя их тогда найти с помощью производной?
Продам формулу с доказательством, что выявляет следующее простое число , подставь вы туда любое простое число !
Простые числа это… просто?