18 Ekim 2016 Salı

Soru 7

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?

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?

Python Kodu

Alternatif çözüm 1 için
Alternatif çözüm 2 için

For alternative solution 1 
For alternative solution 2

3 yorum:

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

    You 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

    YanıtlaSil
    Yanıtlar
    1. 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.

      Thank 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)

      Sil
    2. Attention please. This is an apology...

      Working 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!

      Sil