простые числа

ivan-z · Сообщение **ivan-z** » 10 дек 2011, 14:35

Вопрос:существует ли простая функция,распределяющая простые числа в натуральном ряду.

Andrew58 · Сообщение **Andrew58** » 10 дек 2011, 14:43

ivan-z писал(а):Source of the post
Вопрос:существует ли простая функция,распределяющая простые числа в натуральном ряду.

Насколько простая и насколько точно? В нулевом приближении и равномерная плотность распределения может сгодиться...

Sonic86 · Сообщение **Sonic86** » 10 дек 2011, 15:16

ivan-z писал(а):Source of the post Вопрос:существует ли простая функция,распределяющая простые числа в натуральном ряду.

Что такое "функция, распределяющие числа"?
Вообще, берите Прахара или Титчмарша и читайте себе на здоровье.

ivan-z · Сообщение **ivan-z** » 10 дек 2011, 18:41

Спасибо за ответ,но я имел ввиду элементарную функцию подобно y=ax+b,крторая задавала бы простые числа.О плотности распределения я слава Богу и так знаю.Просто я натолкнулся на примитивную функцию которая при соблюдении определённого условия даёт одни простые числа.Пока я проверил генерацию до миллиона,исключений нет.

vicvolf · Сообщение **vicvolf** » 10 дек 2011, 21:29

Т.е у вас есть элементарная функция, которая дает точное значение миллиона простых чисел. Сомневаюсь! Какая?

omega · Сообщение **omega** » 10 дек 2011, 21:30

ivan-z писал(а):Source of the post
Просто я натолкнулся на примитивную функцию которая при соблюдении определённого условия даёт одни простые числа.Пока я проверил генерацию до миллиона,исключений нет.

А это определённое условие не такое, случайно: "Все значения функции, не являющиеся простыми числами, отбрасываем"? (шутка)

И что означает "примитивную функцию"?

Из истории известны, например, квадратные трёхчлены Эйлера, которые достаточно плотно дают простые числа. Наверное, ещё какие-то функции известны (я мало читала по этому вопросу).

Но вот чтобы была такая элементарная функция, которая давала бы все простые числа уже до миллиона, это вряд ли. Я сомневаюсь пока не увижу такую функцию здесь.

На форуме dS давно уже видела сногсшибательные формулы генерации простых чисел.

Пока писала сообщение, впереди появился ещё один сомневающийся

bot · Сообщение **bot** » 11 дек 2011, 04:56

ivan-z писал(а):Source of the post
Просто я натолкнулся на примитивную функцию которая при соблюдении определённого условия даёт одни простые числа.

Давно известно, что функция $$p(n)$$

, перечисляющая все простые числа в натуральном порядке, примитивно рекурсивна. Что в Вашем понимании есть примитивная функция?

Sonic86 · Сообщение **Sonic86** » 11 дек 2011, 05:10

ivan-z писал(а):Source of the post Спасибо за ответ,но я имел ввиду элементарную функцию подобно y=ax+b,крторая задавала бы простые числа.

Простых таких функций нет (напр, легко доказать, что любой многочлен от одной переменной выдает сколь угодно много составных чисел). Добавление возведения в степень тоже ничего не меняет. В книге "Живые числа" есть несколько функций и алгоритмов, но они довольно сложные. Бывают и более странные (рекуррентная формула с использованием gcd). Есть формула Вешеневского, которая является формульной записью решета Эратосфена (поэтому толку от нее нет, я ее когда увидел - поржал).

ivan-z писал(а):Source of the post Просто я натолкнулся на примитивную функцию которая при соблюдении определённого условия даёт одни простые числа.Пока я проверил генерацию до миллиона,исключений нет.

о! :blink: а можно посмотреть?

ivan-z · Сообщение **ivan-z** » 11 дек 2011, 05:27

число р=
$\sqrt{(6x+1)^2}$
является простым при x не равно 6yz-y-z
понятия не имею имеет ли какое-то значение то,что я написал,но теперь у вас есть возможность проверить.в любом случае спосибо за участие.

Sonic86 · Сообщение **Sonic86** » 11 дек 2011, 05:33

Кажется это просто решето Сундарама, 2-е решето после решета Эратосфена (корень не нужен), только коэффициент другой, просто подставляем и выделяем множители.
[url=http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%...%B0%D0%BC%D0%B0]http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%...%B0%D0%BC%D0%B0[/url]
т.е. какбе боян

yourdomain.com