Ваш диапазон составляет всего десять миллионов, что мало для такого рода вещей. У меня есть два предложения:
1) Создайте таблицу pi (n) с удобными интервалами, затем используйте сегментированное решето Эратосфена для подсчета простых чисел между двумя записями таблицы, которые заключают желаемое значение в скобки. Размер интервала определяет как размер требуемой таблицы, так и скорость, с которой могут быть вычислены результаты.
2) Используйте функцию Лежандра phi (x, a) и формулу подсчета простых чисел Лемера, чтобы вычислить результат напрямую. Функция phi требует некоторого хранилища, я не уверен, сколько именно.
Из двух я бы, вероятно, выбрал первую альтернативу, учитывая размер вашей проблемы. Реализации как сегментированного сита Эратосфена, так и Функция подсчета простых чисел Лемера доступна в моем блоге.
РЕДАКТИРОВАТЬ 1:
Поразмыслив, у меня есть третья альтернатива:
3) Используйте логарифмический интеграл, чтобы оценить pi (n). Он монотонно возрастает и всегда больше, чем pi (n) в течение необходимого вам интервала. Но различия небольшие, никогда не превышают 200. Таким образом, вы можете предварительно вычислить различия для всех значений меньше десяти миллионов, составить таблицу из 200 точек изменения, а затем, когда потребуется, вычислить логарифмический интеграл и найти поправочный коэффициент в Таблица. Или вы можете сделать что-то подобное с функцией R Римана.
Третья альтернатива занимает меньше всего места, но я подозреваю, что место, необходимое для первой альтернативы, не будет слишком большим, и просеивание, вероятно, происходит быстрее, чем вычисление логарифмического интеграла. так что я буду придерживаться своей первоначальной рекомендации. Реализация логарифмического интеграла и функции Riemann R представлена в моем блоге.
РЕДАКТИРОВАТЬ 2:
Как показывают комментарии, это не сработало. Пожалуйста, проигнорируйте мое третье предложение.
В качестве наказания за мою ошибку в предложении решения, которое не работает, я написал программу, которая использует таблицу значений пи (n) и сегментированное решето Эратосфена для вычисления значений пи (n) для n ‹10000000. I Я буду использовать Python, а не C, запрошенный исходным плакатом, потому что Python проще и легче читать в педагогических целях.
Начнем с вычисления простых чисел просеивания, меньших квадратного корня из десяти миллионов; эти простые числа будут использоваться как при построении таблицы значений pi (n), так и при выполнении сита, которое вычисляет окончательный ответ. Корень квадратный из десяти миллионов равен 3162,3. Мы не хотим использовать 2 в качестве простого числа просеивания - мы будем просеивать только нечетные числа и рассматривать 2 как особый случай - но мы хотим, чтобы следующее простое число было больше квадратного корня, так что список просеивание простых чисел никогда не исчерпывается (что могло бы вызвать ошибку). Итак, мы используем эту очень простую версию сита Эратосфена для вычисления простых чисел просеивания:
def primes(n):
b, p, ps = [True] * (n+1), 2, []
for p in xrange(2, n+1):
if b[p]:
ps.append(p)
for i in xrange(p, n+1, p):
b[i] = False
return ps
Сито Эратосфена состоит из двух частей. Сначала составьте список чисел, меньших целевого числа, начиная с 2. Затем несколько раз просмотрите список, начиная с первого неперечеркнутого числа, и вычеркните все кратные числа из списка. Изначально 2 - это первое неперечеркнутое число, поэтому вычеркните 4, 6, 8, 10 и так далее. Тогда 3 будет следующим неперечеркнутым числом, поэтому вычеркните 6, 9, 12, 15 и так далее. Затем 4 было зачеркнуто как кратное 2, и следующее неперечеркнутое число - 5, поэтому вычеркните 10, 15, 20, 25 и так далее. Продолжайте, пока не будут учтены все неперечеркнутые числа; числа, которые не перечеркнуты, являются простыми. Цикл на p рассматривает каждое число по очереди, и если он не перечеркнут, цикл на i вычеркивает кратные.
Функция primes возвращает список из 447 простых чисел: 2, 3, 5, 7, 11, 13, ..., 3121, 3137, 3163. Мы вычеркиваем 2 из списка и сохраняем 446 простых чисел просеивания в глобальной переменной ps:
ps = primes(3163)[1:]
Основная функция, которая нам понадобится, считает простые числа в диапазоне. Он использует сито, которое мы будем хранить в глобальном массиве, чтобы его можно было повторно использовать вместо перераспределения при каждом вызове функции count:
sieve = [True] * 500
Функция count использует сегментированное решето Эратосфена для подсчета простых чисел в диапазоне от lo до hi (lo и hi оба включены в диапазон). Функция имеет четыре for цикла: первый очищает сито, последний подсчитывает простые числа, а два других выполняют просеивание аналогично простому сито, показанному выше:
def count(lo, hi):
for i in xrange(500):
sieve[i] = True
for p in ps:
if p*p > hi: break
q = (lo + p + 1) / -2 % p
if lo+q+q+1 < p*p: q += p
for j in xrange(q, 500, p):
sieve[j] = False
k = 0
for i in xrange((hi - lo) // 2):
if sieve[i]: k += 1
return k
Ядром функции является цикл for p in ps, который выполняет рассев, принимая по очереди каждое простое просеивание p. Цикл завершается, когда квадрат просеивающего простого числа больше, чем предел диапазона, поскольку все простые числа будут идентифицированы в этой точке (причина, по которой нам понадобилось следующее простое число больше квадратного корня, состоит в том, что было бы просеивающее простое число чтобы остановить цикл). Загадочная переменная q - это смещение в решето наименьшего кратного p в диапазоне от lo до hi (обратите внимание, что это не наименьшее кратное p в диапазоне, а индекс смещения наименьшего кратного p в диапазон, который может сбивать с толку). Оператор if увеличивает q, когда он обращается к числу, которое является полным квадратом. Затем петля на j снимает с сита точки, кратные p.
Мы используем функцию count двумя способами. Первое использование создает таблицу значений пи (п), кратных 1000; второе использование интерполирует в пределах таблицы. Сохраняем таблицу в глобальной переменной piTable:
piTable = [0] * 10000
Мы выбираем параметры 1000 и 10000 на основе исходного запроса, чтобы использовать память в пределах пятидесяти килобайт. (Да, я знаю, что исходный плакат смягчил это требование. Но мы все равно можем его соблюдать.) Десять тысяч 32-битных целых чисел займут 40 000 байт памяти, а для просеивания в диапазоне всего 1000 от lo до hi потребуется всего 500 байт. памяти и будет очень быстро. Вы можете попробовать другие параметры, чтобы увидеть, как они влияют на использование пространства и времени программой. Создание piTable осуществляется путем вызова count функции десять тысяч раз:
for i in xrange(1, 10000):
piTable[i] = piTable[i-1] + \
count(1000 * (i-1), 1000 * i)
Все вычисления до этого момента могут выполняться во время компиляции, а не во время выполнения. Когда я проводил эти вычисления на ideone.com, они занимали около пяти секунд, но это время не учитывается, потому что это можно сделать раз и навсегда, когда программист впервые напишет код. Как правило, вам следует искать возможности для перемещения кода из среды выполнения во время компиляции, чтобы ваши программы выполнялись очень быстро.
Осталось только написать функцию, которая фактически вычисляет количество простых чисел, меньших или равных n:
def pi(n):
if type(n) != int and type(n) != long:
raise TypeError('must be integer')
if n < 2: return 0
if n == 2: return 1
i = n // 1000
return piTable[i] + count(1000 * i, n+1)
Первый оператор if выполняет проверку типа. Второй оператор if возвращает правильный ответ на нелепый ввод. Третий оператор if обрабатывает 2 специально; наше рассевание делает 1 простым, а 2 - составным, оба из которых неверны, поэтому мы исправляем здесь. Затем i вычисляется как наибольший индекс piTable, меньший запрошенного n, и оператор return добавляет значение из piTable к количеству простых чисел между значением таблицы и запрошенным значением; предел hi равен n + 1, потому что в противном случае в случае, если n простое, оно не будет засчитано. Например, скажем:
print pi(6543223)
вызовет отображение числа 447519 на терминале.
Функция pi работает очень быстро. На ideone.com тысяча случайных вызовов pi (n) вычислялась примерно за полсекунды, то есть примерно половина по миллисекунде каждый; это включает время для генерации простого числа и суммирования результата, поэтому время на фактическое вычисление функции Пи составляет даже менее половины миллисекунды. Это довольно хорошая окупаемость наших инвестиций в создание стола.
Если вас интересует программирование с простыми числами, я довольно много поработал в своем блоге. Пожалуйста, приходите и заходите.
person
user448810
schedule
02.01.2013
