10001st prime
Problem 7
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10 001st prime number?
Alternatif çözüm 1 için What is the 10 001st prime number?
10001 nci asal
Soru 7
2, 3, 5, 7, 11, ve 13 olarak llk altı asal sayıyı listelediğimizde, 6 ıncı asal sayının 13 olduğunu görebiliriz.
10 001inci asal sayı kaçtır?
10 001inci asal sayı kaçtır?
Python Kodu
Alternatif çözüm 2 için
For alternative solution 1
For alternative solution 2
Program is fine but you are controlling every number from 2 to x for division, which is not cool :) Because for prime numbers until x this works in O(x^2), which is large.
YanıtlaSilYou can make the outer loop go by 2, since all primes are odd(except 2) and make the primality test by looking dividends until square root of(x) because the dividends are symmetrical to a numbers square root.
This will decrease your working time from x^2 to x*sqrt(x)/4
After finding out about the 1 minute rule (https://projecteuler.net/ : I've written my program but should it take days to get to the answer?), I've decided to update my answer since it was taking extremely long to halt.
SilThank you for your advice on making the outer loop go by 2 which has also been given by my friend Ceyhan. It makes the code run slightly faster indeed. But I can't say the same about the square roots. It is true that the time complexity decreases with your proposal, but you should also bear in mind that the calculation of square root has its own weight on CPU. Please have a look at the Gist I have created regarding this issue. (https://gist.github.com/BedirYilmaz/d0bffef11e0380b17c6ac9a2b74d5d7a)
Bir dakika kuralını (https://projecteuler.net/ : I've written my program but should it take days to get to the answer?) öğrendikten sonra kodumda bir güncellemeye gitmek istedim, zira durması hayli uzun zaman alıyordu.
Bu arada dış döngüdeki iterasyon değişkenini ikişer ikişer artırma tavsiyeniz için çok teşekkür ederim, aynı mantıklı tavsiyeyi Ceyhan hocam da yapmıştı, kodun az da olsa hızlanmasını sağladı. Fakat sayıların kareköklerine kadar arama yapmakla ilgili aynı şeyi söyleyemeyeceğim, zira karekök bulma işleminin de kendine ait bir çalışma yükü getirmesi söz konusu. Lütfen konuya ilişkin olarak oluşturmuş olduğum Gist' e bir göz atın. (https://gist.github.com/BedirYilmaz/d0bffef11e0380b17c6ac9a2b74d5d7a)
Attention please. This is an apology...
SilWorking time decreased by using the square root tremendously indeed. I tried to apply the advice you've given before I wrote my previous post, but it turns out that I made a mistake when I was writing it. Have a nice weekend!
Dikkat dikkat! Bu bir özür ifadesidir. Karekökün kullanımı çalışma zamanını ciddi biçimde düşürüyormuş gerçekten. Bir önceki iletimi yazmadan evvel verdiğiniz tavsiyeyi uygulamıştım, fakat kodu yazarken bir hata yapmışım. İyi haftasonları dilerim!