vkomen4 фев 2022 в 19:19

Простые числа это… просто?

3 мин

11K

Алгоритмы * Ненормальное программирование * Программирование *

+28

Комментарии 17

НЛО прилетело и опубликовало эту надпись здесь

raamid 4 фев 2022 в 20:35

Как известно, синус вычисляется через полиномиальный ряд. А что если взять ряд сумм синусов и каждый синус развернуть в полиномиальный ряд. Получится новый ряд, в котором возможно, получится сделать упрощения, а значит сэкономить на вычислениях.

VPryadchenko 5 фев 2022 в 06:10

Позвольте поинтересоваться, а какова постановка задачи и какой вывод? Какие преимущества у вашего подхода и с чем его вообще корректно сравнивать?

vkomen 5 фев 2022 в 06:25

Это просто наблюдение. Непонятно, почему плодятся простые, непонятно, почему между ними проскакивают составные)

AxelLx 5 фев 2022 в 09:03

Да, простые числа — это просто.
Ваши дроби получаются из суммы обратных первым n простым числам.
$\bg_white \sum \pm \frac{1}{p_i}= \frac{1 \times p_2\times p_3\times \cdots \times p_{n-1} \times p_{n} + p_1\times 1 \times p_3\times \cdots \times p_{n-1} \times p_{n} + \cdots + p_1\times p_2\times \cdots \times p_{n-2} \times 1 \times p_{n} + p_1\times p_2\times \cdots \times p_{n-2} \times p_{n-1} \times 1}{\prod p_i}$
В числителе все слагаемые кроме одного делятся на p_1, все, кроме одного делятся на p_2 и т.д… Следовательно, числитель не делится на первые n простых.

Получилось обычное решето Эратосфена.

vkomen 5 фев 2022 в 09:28

Почему тогда составные проскакивают???

AxelLx 5 фев 2022 в 09:37

Числитель не делится на первые n простых, но может делиться на p_{n+1}, p_{n+2} и т.д.

wataru 5 фев 2022 в 09:09

Вы открыли замечательный факт, что GCD(abс, x) = 1 для чисел, не делящехся на a, b, c.

При раскрытии через сумму вы получаете, что знаменатель — произведение всех ваших простых чисел, а в числителе отсаются взаимно простые.

Далее, с учетом, что любое составное число имеет делитель не превосходящий его корень, вы можете таким методом "найти" все простые до sqrt(abc). Так что, если в вашей таблице возьмете корнень из "максимальное", то у вас останутся только простые числа в этом интервале. А выше этого предела — уж как повезет. Там могут выпасть и простые числа, но в основном будут составные.

Ваш метод есть обобщение эвристики — перебирать в решете только нечетные числа. Или только числа вида 6k+1 и 6k+5.

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

MrAlone 5 фев 2022 в 15:59

Извините, но судя по КДПВ, 5 не является простым числом. Мы что-то не знаем?

Ramzai777 29 апр 2022 в 05:36

А 1 является простым числом. Мы точно чего-то не знаем!!!

Grigorenkovic 6 фев 2022 в 13:14

Когда-то очень интересовался этой задачей и разгадкой. Дошел до того, что попробовал установить последовательность непростых чисел, тех которые имеют одинаковую структуру с простыми (6х+-1). Она, получается, есть, но одной формулой никак не выводилась, потому что непонятно на каждом отрезке, какое количество будет 5 и 7 (5х+7у)

demsp 10 фев 2022 в 05:55

Он пытается преобразовать произведение в сумму!

А простые находятся в экстремумах функции (судя по графику)? А нельзя их тогда найти с помощью производной?

vkomen 30 мар 2022 в 05:59

Нет, функция не определена аналитически на всей оси... Тоже об этом думал, но - увы

demsp 24 сен 2023 в 07:32

спасибо за уточнение :)

Raha37 29 апр 2022 в 05:36

Продам формулу с доказательством, что выявляет следующее простое число , подставь вы туда любое простое число !

Зарегистрируйтесь на Хабре, чтобы оставить комментарий