n tane O(n√n)
Ancak görüşmeci, dış bandın sadece n becere gitmediğini söyledi örneğin, ilk 100 asal sayıları bulmak için, örneğin 541'e (100. asal sayı) dönelim.Karmaşıklık ilk bu sorulara verilen röportajda asal sayı
Peki, verilen zaman karmaşıklığını nasıl ifade edebiliriz?
Bunun yanıtı, yüksek matematik, yani asal sayıların dağıtım yasasını alır. Size (https://en.wikipedia.org/wiki/Prime_number_theorem) n -th asal sayı değerinin n.log(n) olduğunu bildirir.
Ardından karmaşıklığınız O(n√n.log(n)√log(n))'dur.
Bu sınırın kötümser olduğunu söyleyebilirim, çünkü tüm yineleme işlemleri untiln'ye kadar devam etmez. Örneğin, hemen numaralar bile tespit edilir. Daha sıkı bir bağ için, tamsayıların en küçük faktörünün dağıtım kanununa ihtiyacınız olacaktır.
Çok iyi bilinen bir gerçektir. RSA'yı kapsayan bir kriptografi kursu alsaydın, bunun hakkında bir şeyler öğrenirdin. Belki de CV'nizde (örneğin, kriptografi) böyle bir şey iddia ettiniz ve sonra sizi bu konuda test etmeye karar verdiler. – blazs
Katılıyorum. “Cevabını kesin bir şekilde veremedim çünkü” n ”ve“ n ”prime arasındaki ilişkiyi bilmiyorum. –
@Yves: –
Bir yan not olarak: 'Math.sqrt()' sözcüğünü çağırmak ve tür yazmak yerine 'divison * divisor <= number' değerini görmeyi tercih ederim. – blazs