Как найти число простых чисел?

Question

Мне нужно найти определенное количество простых чисел. У меня есть рабочий алгоритм, который принимает числовой предел как параметр - он находит все простые числа, которые меньше предела.

Например, для параметра 20 он вернет 2,3,5,7,11,13,17,19, но мне нужно ввести 5 и получить 2,3,5,7,11. Каков наилучший способ? Я использую Сито Эратосфена, и нет возможности ограничить часть удаления числа, так как я не знаю, насколько велико большое число 195-го числа, и поэтому я не знаю, следует ли удалять все кратные 2 до 1568 или 1268426. Надеюсь, что вопрос ясен, спасибо за помощь

Answer 1

Существует несколько способов сделать то, что вы хотите.

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

Вместо приближения имеются формулы, которые вычисляют точное число простых чисел менее n без перечисления простых чисел. Вы можете использовать одну из этих формул, чтобы найти n th prime, затем используйте сито, чтобы составить список простых чисел. Google для «суммы Лежандра» и «формулы Лемера», если вы хотите воспользоваться этим подходом.

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

Существует очень умный способ создания бесконечного списка простых чисел, который заменяет бит-массив Сита Эратосфена приоритетной очередью. Google для бумаги Мелиссы О'Нейл Подлинное сито Эратосфена.

Вы можете увидеть полные объяснения и реализации всех этих алгоритмов here.

Кстати, 195-й премьер является 1187. Есть 247 простых чисел меньше, чем 1568, и 97790 простых чисел меньше 1268426.

Answer 2

Вы можете взять ту же идею за оригинальное сито Эратосфена, но делайте это итеративно.

find_n_primes(num_primes): 
    primes = [2] 
    i = 3 
    while primes.size < num_primes: 
    is_prime = true 
    for p in primes: 
     if p > sqrt(i): 
     break 
     if i % p == 0: 
     is_prime = false 
     break 
    if is_prime: 
     primes.add(i) 

    i++ 
    return primes 

В принципе, вместо того, кратные каждое число до фиксированной точки, перебирать п, и проверить все простые числа, вы уже нашли, вместо этого.

Answer 3

Некоторое время назад я написал небольшой модуль, который имеет дело с простыми числами (который служил мой при работе над материалом Project Euler). Это довольно быстро, потому что он отслеживает список простых чисел, которые он видел. Это значительно сокращает время вычисления.

Это основная процедура, которая вам понадобится (написана на python). Документация посредственная, но я надеюсь, что это поможет.

def primes(num, l=[]): 

    # l is the list of prime numbers you already have 
    # This is reused to check for primality of a number 

    if len(l) == 0: l = get_list() # Read from disk 

    # Check to see if a sublist can be created 
    e = l[-1] 
    if (num < e): 
     res = search.binary_low(l, num) 
     return l[:res[0]+1] 

    e = 6*(ceil(e/6)) 

    lim = num + 1 
    # Extend the current list 
    for n in range(e, lim, 6): 
     m = n - 1 
     if isprime(m, l): l.append(m) 
     m = n + 1 
     if isprime(m, l): l.append(m) 

    # Save to pickle 
    set_list(l) # Write to disk 

    return l 

Вы можете найти соответствующие процедуры над здесь

https://github.com/pavanky/expo/blob/master/python/prime.py

https://github.com/pavanky/expo/blob/master/python/search.py