Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 19 20 21 22 23 [24] 25 26 27 28 .. 31   вперед  Ctrl
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
alex55555
Member

Откуда:
Сообщений: 2095
Gennadiy Usov
Суть алгоритма поиска простых чисел на отрезке следующая.

Вы про ограничение по памяти-то помните? Или опять забыли?
11 мар 19, 12:42    [21829033]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
alex55555
Gennadiy Usov
Суть алгоритма поиска простых чисел на отрезке следующая.
Вы про ограничение по памяти-то помните? Или опять забыли?
Если бы Вы дочитали сообщение до конца, то поняли бы, что речь идет о формуле количества простых чисел.

При этом в предыдущих сообщениях была попытка представить один очень длинный ряд чисел в виде короткого выражения - формулы.

А как известно, для расчета по формуле не требуется очень большая память.
11 мар 19, 14:10    [21829188]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
С другой стороны, попытка найти формулу пересчета простых чисел по методу ОТА оказалась неудачной.
Хотя были интересные наработки.

Рассматривался гармонический ряд:
Н=1+1/2+1/3+1/4+1/5+1/6+1/7.......
Существует формула Эйлера по определению числа Н
Н=ln(Н)++0,5772... (постоянная Эйлера) + е (некотороя величина, которая при увеличении Н стремится к бесконечности.

Из гармонического ряда можно выделить последовательность
НС=1/5+1/7+1/11+1/13...
На компьютере удалось найти формулу:
Нс=Н х 0,38..... - 1

То есть, находится количество составных чисел, получающихся от использование метода ОТА.
Осталось отнять эти составные числа от всех чисел 6хК+1 и 6хК+5.
Их будет 6 х N.

Но это оказалось всё неверно, так как некоторые составные числа считались по несколько раз21828897.

Поэтому нет смысла дальше разрабатывать ОТА, а вернуться к методу БРЧ.
11 мар 19, 14:50    [21829233]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
Gennadiy Usov
Осталось отнять эти составные числа от всех чисел 6хК+1 и 6хК+5.
Их будет 6 х N.
Ошибка.

следует читать:
Осталось отнять эти составные числа от всех чисел 6хК+1 и 6хК+5.
Таких чисел, как 6хК+1 и 6хК+5, будет N/3.

N - общее количество последовательных чисел от 1.
11 мар 19, 14:54    [21829239]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9133
Gennadiy Usov
А как известно, для расчета по формуле не требуется очень большая память.
Если вы нашли формулу простых чисел, то вам прямая дорога в Нобелевский комитет.

P.S.
Это был сарказм, если без смайликов непонятно.
11 мар 19, 14:56    [21829241]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
Basil A. Sidorov
Gennadiy Usov
А как известно, для расчета по формуле не требуется очень большая память.
Если вы нашли формулу простых чисел, то вам прямая дорога в Нобелевский комитет.
P.S.
Это был сарказм, если без смайликов непонятно.
Эта формула, которую я пытался получить, не формула расчета простых чисел, а формула расчета количества простых чисел.
11 мар 19, 15:00    [21829245]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9133
Gennadiy Usov
... а формула расчета количества простых чисел.
Здесь тоже будет сарказм.

P.S.
Да, вот такая я злобная сволочь.
11 мар 19, 15:04    [21829251]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
Basil A. Sidorov
Gennadiy Usov
... а формула расчета количества простых чисел.
Здесь тоже будет сарказм.
P.S.
Да, вот такая я злобная сволочь.
Могу Вас успокоить - формула не получилась...
11 мар 19, 15:07    [21829255]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 40510
Gennadiy Usov
Basil A. Sidorov
пропущено...
Если вы нашли формулу простых чисел, то вам прямая дорога в Нобелевский комитет.
P.S.
Это был сарказм, если без смайликов непонятно.
Эта формула, которую я пытался получить, не формула расчета простых чисел, а формула расчета количества простых чисел.

В пределе формула плотности n/ln(n) достаточно точна. Зачем вам выводить частные формулы?
11 мар 19, 15:10    [21829261]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
mayton
Gennadiy Usov
Эта формула, которую я пытался получить, не формула расчета простых чисел, а формула расчета количества простых чисел.
В пределе формула плотности n/ln(n) достаточно точна. Зачем вам выводить частные формулы?
А как она точна на больших N? В %.
На малых N % большой21828639.

Всегда где-то витает идея.
Посмотрел на проблему с другой стороны.
Заинтересовали формулы...
11 мар 19, 15:15    [21829272]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 40510
Gennadiy Usov
mayton
пропущено...
В пределе формула плотности n/ln(n) достаточно точна. Зачем вам выводить частные формулы?
А как она точна на больших N? В %.
На малых N % большой21828639.

Всегда где-то витает идея.
Посмотрел на проблему с другой стороны.
Заинтересовали формулы...

Ты что-то не то посчитал. Мы с Димой проверяли эту формулу в топиках несколько лет назад - она
аппроксимировала число простых довольно точно.

Покажи свои расчеты.
11 мар 19, 16:13    [21829370]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Dima T
Member

Откуда:
Сообщений: 13634
mayton
Мы с Димой проверяли эту формулу в топиках несколько лет назад - она
аппроксимировала число простых довольно точно.

Не проверяли особо, просто прикинули что похоже на правду.

Проверил, точные данные отсюда 21189904
NПростых 1...NN/ln(N)Отношение
982 451 65350 000 00047 448 68494.9%
2 038 074 743100 000 00095 080 42695.1%
11 037 271 757500 000 000477 296 84595.5%
22 801 763 4891 000 000 000956 044 62695.6%
47 055 833 4592 000 000 0001 914 815 79295.7%
71 856 445 7513 000 000 0002 874 495 13095.8%
11 мар 19, 16:28    [21829405]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 40510
94% - прекрасная пропорция. Что еще надо?
11 мар 19, 16:34    [21829423]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Dima T
Member

Откуда:
Сообщений: 13634
mayton
94% - прекрасная пропорция. Что еще надо?

Вполне достаточно для предварительной оценки.
11 мар 19, 16:36    [21829427]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 40510
Достаточна даже для выборов.
11 мар 19, 16:43    [21829445]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Barlone
Member

Откуда:
Сообщений: 1187
N / ln N + N / (ln N)2 + (2*N) / (ln N)3
11 мар 19, 17:56    [21829557]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 40510
Почему до 3-й степени? Хм... непонятно.
11 мар 19, 19:45    [21829689]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4487
mayton,

Теорема о распределении простых чисел
11 мар 19, 19:58    [21829702]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 40510
kealon(Ruslan)
mayton,

Теорема о распределении простых чисел

Можете конкретнее подсказать где лежит ответ на мой вопрос? Мне тяжело читать много математических выкладок.
11 мар 19, 20:22    [21829725]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Dima T
Member

Откуда:
Сообщений: 13634
В любом случае точность не 100%, а если так, то +/- 5% особо ничем не отличается от +/-0.0001%. Все-равно с погрешностью.
11 мар 19, 20:32    [21829740]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4487
mayton
kealon(Ruslan)
mayton,

Теорема о распределении простых чисел

Можете конкретнее подсказать где лежит ответ на мой вопрос? Мне тяжело читать много математических выкладок.
он просто 3 написал
на самом деле ряд бесконечный

там надо связать ряд обратных квадратов и формулу с Теорема о распределении простых чисел
11 мар 19, 20:39    [21829745]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 40510
С нашими грубыми оценками... нам достаточно и первого члена.
Нам по сути даже не надо считать. А оценить принципиальную возможность.
Взлетают реперные числа или нет. А если взлетают то сколько им надо памяти?

Я предоставил таблицы действующих технических ограничений. Это - первый рубеж.
Не вылезайте. Вылезли - почти убежден ваша идея уже не работает. Так устроены
современные технологии.

В книге - Практическая Криптография Брюс Шнайер оперирует еще более грубыми
сравнительными оценками. Но ему их достаточно.

Поэтому точность 94% - хватит с головой. Как-то так.
12 мар 19, 00:37    [21829880]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
Нашел интересную последовательность.

Все до сих пор рассматривали последовательность в виде:
произведение последовательных простых чисел от 1.

Я предлагаю немного изменить эту последовательность:
произведения последовательных простых чисел от 1, делённая на 2, и плюс или минус 2.

Оказалось, что для 1 и 2 имеем 1 и 5,
Для 1,2,3 - 13 и 17
для 1,2,3,5 - 103 и 107
для 1,2,3,5,7 - 1153 (1157 - нет)
для 1,2,3,5,7,11 - 15013 и 15017
для 1,2,3,5,7,11,13 - 255253, (255257 - нет)
для 1,2,3,5,7,11,13,17 - (4849847 - нет) 4849843
далее:
(111546437- нет) 111546433
3234846617 (3234846613-нет)
100280245067 100280245063
3710369067407 (3710369067403-нет)
(152125131763607-нет) 152125131763603

Далее не позволяет "ячейка"

Кто-нибудь продолжит?

Кстати, и диапазоны здесь небольшие, следующее число (мимо того, которое "нет"), наодится через 2 - 5 шагов по системе 2,4.
12 мар 19, 07:18    [21829924]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 40510
А какую задачу вы решаете теперь?

Я почему спрашиваю. Топика стартовал как генерация последовательности primes методом Эратосфена.
12 мар 19, 10:08    [21829978]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
mayton
А какую задачу вы решаете теперь?
Я почему спрашиваю. Топика стартовал как генерация последовательности primes методом Эратосфена.
А это и есть продолжение идеи Эратосфена.

При определении различных БРЧ, построеных на идее Эратосфена, было замечено, что по краям этих БРЧ есть "дыры", где нет простых чисел.
Поскольку распределение простых чисел почти равномерное на диапозоне, то можно предположить, что в других местах БРЧ распределение простых чисел будет чаще.

Самое простое решение этой проблемы, это - определять простые числа рядом с серединой БРЧ.

Что и было показано на БРЧ, начиная с БРЧ-2-3 и заканчивая БРЧ-13-41.
Далее - маловата ячейка.
12 мар 19, 11:18    [21830022]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 19 20 21 22 23 [24] 25 26 27 28 .. 31   вперед  Ctrl
Все форумы / Программирование Ответить