Найти положение простого номера

Ответ 1

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

1) Создайте таблицу pi (n) с удобными интервалами, затем используйте сегментированное сито Eratosthenes для подсчета простых чисел между двумя табличными элементами, которые скобят желаемое значение. Размер интервала определяет как размер требуемой таблицы, так и скорость, с которой результаты могут быть вычислены.

2) Используйте функцию Legendre phi (x, a) и формулу простого подсчета Lehmer для вычисления результата напрямую. Для phi-функции требуется некоторое хранилище, я точно не знаю, сколько.

Из двух я бы выбрал первую альтернативу, учитывая ваш размер проблемы. Реализации как сегментированного сита Эратосфена и Lehmer's - функция подсчета доступна в моем блоге.

ИЗМЕНИТЬ 1:

При отражении у меня есть третья альтернатива:

3) Используйте логарифмический интеграл для оценки pi (n). Он монотонно возрастает и всегда больше pi (n) в течение требуемого интервала. Но различия незначительны, но не более 200. Таким образом, вы можете прекомпретировать различия для всех значений менее десяти миллионов, составить таблицу из 200 пунктов смены, затем, когда запросите, вычислите логарифмический интеграл и найдите поправочный коэффициент в Таблица. Или вы можете сделать что-то подобное с функцией Римана R.

Третий вариант занимает наименьшее пространство, но я подозреваю, что пространство, требуемое для первого варианта, не будет слишком большим, а просеивание, вероятно, быстрее, чем вычисление логарифмического интеграла. поэтому я буду придерживаться своей первоначальной рекомендации. Существует реализация как логарифмического интеграла, так и функции Римана R в в моем блоге.

ИЗМЕНИТЬ 2:

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

В качестве покаяния за мою ошибку, предлагая решение, которое не работает, я написал программу, которая использует таблицу значений pi (n) и сегментированное сито Eratosthenes для вычисления значений pi (n) для n < lt; 10000000. Я буду использовать 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 рассматривает каждое число по очереди, а если оно не пересекается, цикл на я пересекает кратные.

Функция primes возвращает список из 447 простых чисел: 2, 3, 5, 7, 11, 13,..., 3121, 3137, 3163. Мы удаляем 2 из списка и храним 446 просеивающих чисел в глобальная переменная ps:

ps = primes(3163)[1:]

Основная функция, которая нам понадобится, подсчитывает простые числа в диапазоне. Он использует сито, которое мы будем хранить в глобальном массиве, чтобы его можно было повторно использовать, а не перераспределять при каждом вызове функции count:

sieve = [True] * 500

Функция count использует сегментированное сито Eratosthenes для подсчета простых чисел в диапазоне от 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 в диапазоне от h до (h) (обратите внимание, что он не является наименьшим кратным p в диапазоне, но индекс смещения наименьшего кратного p в диапазон, который может ввести в заблуждение). Оператор if увеличивает q, когда он ссылается на число, являющееся идеальным квадратом. Тогда петля на j удаляет кратные p из сита.

Мы используем функцию count двумя способами. Первое использование строит таблицу значений pi (n) с кратным 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 составным, оба из которых неверны, поэтому мы исправим здесь. Тогда я вычисляется как наибольший индекс piTable меньше запрошенного n, а оператор return добавляет значение от piTable к числу простых чисел между значением таблицы и запрошенным значением; предел hi равен n + 1, так как в противном случае в случае, когда n является простым, он не будет учитываться. Например, говоря:

print pi(6543223)

приведет к отображению на терминале номера 447519.

Функция pi выполняется очень быстро. В ideone.com тысяча случайных вызовов pi (n) вычислялась примерно через полсекунды, так что примерно половина миллисекунды каждая; который включает в себя время для генерации простого числа и суммирования результата, поэтому время фактического вычисления функции pi составляет менее половины миллисекунды. Это очень хорошая отдача от наших инвестиций в построение таблицы.

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

Ответ 2

Если вы знаете априори, что ввод является простым, вы можете использовать аппроксимацию pi (n) ≈ n/log n с небольшой таблицей исправлений для простых чисел, где округление результата недостаточно для получения правильное значение n. Я думаю, что это ваш лучший выбор в пределах ограничения размера, кроме медленного подхода грубой силы.

Ответ 3

Я бы предположил, что здесь будет работать эвристическая гибридная модель. Храните каждый n-й штрих, а затем выполните линейный поиск с помощью тестирования примитивов. Чтобы ускорить работу, вы можете использовать быстрый и простой тест примитивности (например, тест Fermat с a==2) и прекомпретировать ложные срабатывания. Некоторая тонкая настройка, основанная на максимальном размере ввода и ограничениях на хранение, должна быть легко разработана.

Ответ 4

Вот какой код работает. Вы должны заменить тест primality на основе пробного деления с детерминированным Miller-Rabin, который работает для вашего диапазона ввода. Просеивание, чтобы найти простые числа в соответствующем небольшом диапазоне, будет работать лучше, чем пробное деление, но это шаг в неправильном направлении.

#include <stdio.h>
#include <bitset>
using namespace std;

short smallprimes[549]; // about 1100 bytes
char in[19531]; // almost 20k

// Replace me with Miller-Rabin using 2, 7, and 61.
int isprime(int j) {
 if (j<3) return j==2;
 for (int i = 0; i < 549; i++) {
  int p = smallprimes[i];
  if (p*p > j) break;
  if (!(j%p)) return 0;
 }
 return 1;
}

void init() {
 bitset<4000> siv;
 for (int i = 2; i < 64; i++) if (!siv[i])
  for (int j = i+i; j < 4000; j+=i) siv[j] = 1;
 int k = 0;
 for (int i = 3; i < 4000; i+=2) if (!siv[i]) {
  smallprimes[k++] = i;
 }

 for (int a0 = 0; a0 < 10000000; a0 += 512) {
  in[a0/512] = !a0;
  for (int j = a0+1; j < a0+512; j+=2)
   in[a0/512] += isprime(j);
 }
}

int whichprime(int k) {
 if (k==2) return 1;
 int a = k/512;
 int ans = 1 + !a;
 for (int i = 0; i < a; i++) ans += in[i];
 for (int i = a*512+1; i<k; i+=2) ans += isprime(i);
 return ans;
}

int main() {
 int k;
 init();
 while (1 == scanf("%i", &k)) printf("%i\n", whichprime(k));
}

Ответ 5

Следующее звучит так, как будто вы ищете. http://www.geekviewpoint.com/java/numbers/index_of_prime. Там вы найдете код и модульные тесты. Поскольку ваш список относительно невелик (т.е. 10^7), он должен обрабатывать его.

В основном вы находите все простые числа между 2 и n, а затем подсчитываете все простые числа меньше n, чтобы найти индекс. Кроме того, в случае, если n не является простым, функция возвращает -1.

Ответ 6

Что вы предлагаете лучше всего. Предварительно вычислите (или загрузить) список простых чисел менее 10 ^ 7, затем двоичный поиск их.

Есть только 664579 простых чисел менее 10 ^ 7, поэтому список будет потреблять ~ 2,7 МБ пространства. Бинарный поиск для решения каждого экземпляра будет очень быстрым - всего ~ 20 операций.

Ответ 7

Я сделал именно это один раз. Написал код, который дал n, может быстро найти n-е правое, до n = 203542528, так что примерно 2e8. Или он может вернуться назад, для любого числа n, может определить, сколько простых чисел меньше n.

Используется база данных. Я сохраняю все простые числа до определенной точки (sqrt моего верхнего предела). В вашем случае это означает, что вы сохраните все простые числа до sqrt (1e7). Их насчитывается 446, и вы можете сохранить этот список в сжатой форме, так как максимальная разница до этой точки равна только 34. Помимо этой точки, сохраняйте каждое k-е простое (для некоторого значения k). Тогда достаточно быстрое сито для генерации всех простых чисел за короткий промежуток времени.

Итак, в MATLAB, чтобы найти 1e7'th prime:

nthprime(1e7)
ans =
   179424673

Или, он может найти количество простых чисел меньше 1e7:

nthprime(1e7,1)
ans =
      664579

Дело в том, что такую ​​базу данных легко построить и искать. Если ваша база данных может быть не более 50 тыс., Проблем не должно быть.