Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
3 beğenilme 0 beğenilmeme
1.1k kez görüntülendi
$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?)
Veri Bilimi kategorisinde (470 puan) tarafından  | 1.1k kez görüntülendi

Ö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.

1 cevap

3 beğenilme 0 beğenilmeme
En İyi Cevap

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$

 

 

(2.9k puan) tarafından 
tarafından seçilmiş
20,275 soru
21,804 cevap
73,482 yorum
2,430,913 kullanıcı