$10001$-inci asal sayı kaçtır?

Question

$10001$-inci asal sayıyı nasıl buluruz? (Teker teker kontrol edip bir sayaçla 10001-inci asala kadar kontrol etmek baya yavaş bir hesaplama olduğundan, matematiksel bir kolaylıkla daha hızlı nasıl hesaplarız?)

Comments

https://www.wolframalpha.com/input/?i=10001+th+prime

---

Öyle basit bir formül yok.

Asal sayıları hesaplayan formül var ama çok yavaş hesaplıyor.

Wikipedia da bazıları var. (https://en.wikipedia.org/wiki/Formula_for_primes)

---

Cevabiniza katilmiyorum. En azindan hiz konusunda. Eratosthenes elegi $n$ e kadar olan asallari bulmak icin $O(n\log\log n)$ islem yapiyor. Daha sofistike elekler ile $O(n)$ hatta ve hatta $O(n/\log\log n)$ islem yapmak mumkun. Bildigim kadari ile $n$ inci asal $p_n$ icin soyle bir asimptotik sinir vermek mumkun.
$n\ln n + n(\ln\ln n -1) < p_n < n\ln n + n \ln \ln n$

$n$ inci asal sayiyi bulmak icin $n\ln n + n \ln \ln n$ e kadar bi Eratosthenes elegi uygulayabiliriz.

---

Hız relatifdir :-)

---

O da dogru :D.

Answer 1

En azindan sunu diyebiliriz   $\pi(x)$ finksiyonu $x$'den kucuk kac tane asal oldugunu sayan fonksiyon olsun.

 

Gauss ve Legendre'nin asal sayma fonksiyonunu kullanirsak

$\pi(x)\approx \dfrac{x}{\ln x}=10001\implies x\leq116684$ civarinda oldugunu soyleyebiliriz.

Veya daha iyi sonuc veren

$\pi(x)\approx \text{Li(x)}=\displaystyle\int_2^x\dfrac{1}{\ln t}dt=10001\implies x\geq 104293$

 

Burdan $10001.$ asal sayinin $104293\leq x\leq 116684$ araliginda oldugunu soyleyebiliriz.

 

 

 

 

$p(n)$ fonksiyonu $n.$ asal sayiyi versin.

$p(n)\approx n\ln n$ veya  $p(n)\approx n(\ln n+\ln(\ln n)-1)$ dir.

 

$p(10001)\approx 10001(\ln 10001+\ln(\ln 10001)-1)=104318$