Как найти заданное количество простых чисел? - PullRequest
Новая
       5

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

1 голос
/ 30 января 2012

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

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

Ответы [ 3 ]

5 голосов
/ 30 января 2012

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

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

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

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

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

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

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

0 голосов
/ 30 января 2012

Некоторое время назад я написал небольшой модуль, который работает с простыми числами (который служил моим потребностям при работе над проектом 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

0 голосов
/ 30 января 2012

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

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

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

...