Prime Number Теорема Python

Question

Я пытаюсь поддержать теорему о простых числах, используя прилагаемый код. Я хотел бы как-то показать, что средний разрыв между простыми числами меньше n равен log (n). Код, который у меня есть сейчас, может определить, является ли определенное число простым, а затем вторая часть вычисляет основной пробел для каждого последовательного правого в моем диапазоне. Любые идеи о том, как действовать в python, используя следующий код?

from pylab import * 

def Is_Prime (n): 
    if n==1: 
     return False 
    if n == 2 or n == 3: 
     return True 
    if n == 4: 
     return False 
    if n%2 == 0 or n%3 == 0: 
     return False 

    for i in range(5,int(n**0.5)+1,6): 
     if n%i == 0 or n%(i+2) == 0: 
      return False 

    return True 

k = 0 
for i in range (1,100): 
    if Is_Prime(i) == True: 
     print(i) 
     k+=1 
print "Total number of prime numbers in [1,100] is", k 


previous = 2 
n = 0 
for i in range(3,100000): 
    if Is_Prime(i): 
     n = n+1 
     current = i 
     gn = current - previous 
      print gn 
     plot(n,gn,'rs') 
     xlabel('n') 
     ylabel('g(n)') 
     previous = i 
     if n == 100: 
      break 

show() 

Answer 1

Мое предложение о том, как это сделать (по отношению к текущему коду) выглядит следующим образом:

previous = 2 
n = 0 
for i in range(3,10000000): 
    if Is_Prime(i): 
     n = n+1 
     current = i 
     gn = current - previous 
     previous = i 
     if n % 1000 == 0: 
      print "Now at the gap between prime",n,"and prime",n+1 
      average_gap = (i-2)/float(n); 
      # (n+1)st prime is i, 1st prime is 2. n gaps. 
      # float(n) so that we get float, not int division! 
      print "Average gap so far:", average_gap 
      print "ln(p)/average_gap:", math.log(i)/average_gap 
     if n % 100000 == 0: 
      break 

Обратите внимание, что в 10000th расцвете сил, мы находимся только в соотношении 1,1 МОГ. .. и на 100000-м премьер, мы все еще на 1.0831.

Это занимает время longgg, чтобы приблизиться к 1. Это отчасти потому, что на самом деле более внимательно следит за reciprical функции Li(n): http://en.wikipedia.org/wiki/Logarithmic_integral_function (- как длина щели вокруг n, примерно log(n) ... Таким образом, общее плотность простых чисел ниже n является более подходящим интегралом этого ... Но для больших n, Li(n) ~ log(n), так оно и работает).

(см первый график справа от http://en.wikipedia.org/wiki/Prime_number_theorem - синяя линия представляет собой отношение вы получите, пурпурная линия представляет собой отношение вы бы получить с помощью логарифмического интеграла)

В качестве другого в сторону, (и как я предложил в моем комментарии), было бы также быть намного быстрее, чтобы взглянуть на использование Сита для генерации простых чисел - например, смотрите здесь: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ...

но приведенный выше код работает (по крайней мере для меня)! В любом случае, наилучшие пожелания с вашими будущими первыми начинаниями!