Генерация простых чисел в поливремени

Я изо всех сил пытаюсь понять, как мы можем создать список J наименьших простых чисел в поливремени J, основываясь на том факте, что p'j меньше или равно 2j * ln(j) для j > 2, где j указывает j-е последовательное простое число количество. Например, p1 = 2 для j = 1, p2 = 3 для j = 2, p3 = 5 для j = 3, p4 = 7 для j = 4, p5 = 11 для j = 5 и т. д. и т. д.

Я просто не понимаю, как я могу использовать этот факт выше. Каждый раз, когда я хочу сгенерировать простое число, скажем, 7-е, я проверяю, подставляя: 2(7)*ln(7) = 27,2427... Но, как выясняется, это совершенно бесполезно. Это число намного больше, чем последнее сгенерированное простое число в моем массиве, что логично. Следовательно, мне все еще приходится прибегать к грубой силе, проверяя последнее число +1 на наличие mod0 с каждым из чисел в моем массиве. Другой вариант — прибегнуть к уже существующим алгоритмам, сокращающим время до полиномиального.

Не могли бы вы показать мне, как я могу использовать этот факт: p'j ‹= 2j*ln(j)? Спасибо.


algorithm primes prime-factoring
person Rumen Hristov    schedule 23.11.2014    source источник
comment
p'j меньше или равно 2j * ln(j)? Ты уверен?   -  person Lrrr    schedule 23.11.2014
comment
абсолютно 100% позитив! Ну и добавлю, что это при достаточно большом j. Но практически все, что выше 2, работает.   -  person Rumen Hristov    schedule 23.11.2014
comment
Можешь дать ссылку, я не понял   -  person Lrrr    schedule 23.11.2014
comment
У меня нет ссылки. Это из учебника. Я только что отредактировал qn, чтобы учесть небольшую модификацию: j должно быть больше 2.   -  person Rumen Hristov    schedule 23.11.2014
comment
Согласно Википедии, p_j < j*ln(j) + j*ln(ln(j)) меньше 2j*ln(j).   -  person mostruash    schedule 23.11.2014
comment
Я предполагаю, что это некое упрощенное приближение, вытекающее из показанного в википедии.   -  person Rumen Hristov    schedule 23.11.2014
comment
@RumenHristov Это какое-то задание или из твоего любопытства?   -  person mostruash    schedule 23.11.2014
comment
Это данность, которую я должен использовать позже в задании. И я не понимаю, как этот факт может помочь. Это кажется совершенно неважным.   -  person Rumen Hristov    schedule 23.11.2014
comment
Я думаю, вам нужен еще один факт, подразумевающий, что нижняя граница лучше, чем p_(j-1) + 1. Если бы вы могли использовать тот факт, что p_j > j*ln(j)...   -  person mostruash    schedule 23.11.2014

Ответы (2)


arrow_upward
3
arrow_downward

Чтобы показать, что я могу сгенерировать список первых J простых чисел за время, полиномиальное от J, мне нужно вычислить стоимость того, что я генерирую список.

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

Если бы простые числа были исчезающе редкими, то я не мог бы позволить себе проверять каждое число, начиная с 2, потому что простое перечисление всех этих чисел было бы слишком дорого. Но если я знаю, что J-е простое число не больше 2j*ln(j), я могу, по крайней мере, перечислить их все за полиномиальное время.

На самом деле, если мне нужно сгенерировать J простых чисел, и я начну с того, что возьму первые 2J*ln(J) чисел, и решу проверить каждое число на то, что оно простое, путем деления его на каждое найденное до сих пор простое число, у меня никогда не будет более J простых чисел в наличии в любое время, поэтому я не могу выполнить больше, чем 2J ^ 2 * ln (J) пробных делений. Это не принесет мне никакой награды за эффективность или умные алгоритмы, или даже за четкие границы вычислительных затрат, но это не хуже, чем полиномиальное.

person mcdowella    schedule 23.11.2014
comment
Если бы простые числа были исчезающе редкими, как, например, в случае с 5-гладкими числами (также известными как уродливые числа). - person Will Ness; 24.11.2014

arrow_upward
2
arrow_downward

Возможно, вас сбивает с толку то, что вы думаете, что верхняя граница дает вам метод для прямого создания j-го простого числа или первых j простых чисел. Это не так -- это просто дает вам ограничение размера для набора чисел, которые вам нужно проверить с помощью какого-либо метода, который у вас уже есть, например. пробное отделение.

Если я дам вам список из n-1 чисел 2, 3, ..., n и попрошу вас найти все простые числа в этом списке, вы можете сделать это, используя пробное деление за время O (n ^ 2):

  1. Для каждой пары чисел x и y просто проверьте, делится ли x на y без остатка, и вычеркните y, если это так. Этот шаг занимает O(n^2) и требует O(n) места для отслеживания того, какие числа были вычеркнуты.
  2. Перечислите все числа, которые не были зачеркнуты. Этот шаг равен O(n).

Обратите внимание, что это находит все простые числа ‹= n в O(n^2) для любого положительного значения n. Так, в частности, если нам говорят какое-то значение j, оно будет работать для n = RoundDown(2j log j).

При n = RoundDown(2j log j) этот алгоритм работает за время O((2j log j)^2) = O(j^2 log^2 j), полиномиальное по j, и он должен успешно найти по крайней мере первые j простых чисел, поскольку граница говорит нам, что j-е простое число может быть не более чем RoundDown(2j log j), и мы включили все числа до этого числа включительно в наш входной список. (Он может найти даже больше простых чисел, но при необходимости мы можем отбросить их за линейное время.)

Упражнение: подумайте, почему здесь разрешено округлять в меньшую сторону.

person j_random_hacker    schedule 23.11.2014