Asal sayılar üzerine örnekler

1

Soru 1:10001 ci asal sayıyı bulun ?
Soru 2: 2 milyona kadar olan asal sayıların toplamı kaçtır?
Soruları daha küçük basamaklar için kolaylıkla bulabiliyorum ama sıkıntı istenen büyük bir sayı nasıl bir algoritma kurmalı?
Sorular projecteuler sitesinden alınmıştır

2

İlk soru kolay da ikincisi için yarın düşünürüm.

>>> import sympy
>>> sympy.prime(10001)
104743
3

Alt da hangi algoritmayı kullanıyor acaba? Benim yazdığım çok ağır kaldı

4

Dostum böyle sayma işlemlerini yapacağın zaman bence C dilini kullan.

Örneğin test.c isminde bir dosya açıp içine şunları yazın.

int is_prime(int n){
    for (int i = 2; i < n; i++){
        if (n % i == 0){
            return 0;
        }
    }
    return n;
}

Bu yukarıdaki kodları içeren C dosyasından bir tane DLL dosyası oluşturun.

gcc -shared -Wl,-soname,adder -o test.dll -fPIC test.c

Sonra herhangi bir python dosyası oluşturun ve içine de şu kodları yazın:

from ctypes import CDLL

lib = CDLL("./test.dll")

i = 2
count = 0
while count != 10001:
    if lib.is_prime(i):
        count += 1
    i += 1
else:
    print(i - 1)

Bir diğer yöntem ise, sayma işlemlerinin hepsini C’ye taşımaktır.

int is_prime(int n){
    for (int i = 2; i < n; i++){
        if (n % i == 0){
            return 0;
        }
    }
    return n;
}

int find_prime(int n){
    int i = 2;
    int count = 0;
    while (count != n){
        if (is_prime(i) != 0){
            count += 1;
            if (count == n){
                return i;
            }
        }
        i += 1;
    }
}

Sonra yine bu dosyadan bir DLL dosyası oluşturursunuz ve python dosyanızda şu kodlar yer alır.

from ctypes import CDLL

lib = CDLL("./test.dll")

print(lib.find_prime(10001))

Her iki durumda da farkın muazzam olduğunu göreceksiniz.

Not: Veya @EkremDincel’in paylaştığı kütüphaneyi de kullanabilirsiniz. Hatta o kütüphaneyi kullanmak daha uygun sanki.

1 Beğeni
5

Aslında o kütüphaneyi kullanmak daha iyi, teker teker denemek yerine başka bir algoritma kullanıyorlar diye biliyorum.

6

C ve pythonda kodlar aynıyken c neden daha hızlı fark ney?

7

Hangi algoritmayı kullandıklarını öğrenebilir mıyız?

9

Evet öğrenebiliriz. Biraz karışık gelebilir.

sympy kütüphanesinde ntheory isminde bir dizin var onun içinde generate.py ve primetest.py isminde iki dosya var. Bunların içine bakabilirsiniz.

generate.py 303. satır.

def prime(nth):
    """ Return the nth prime, with the primes indexed as prime(1) = 2,
        prime(2) = 3, etc.... The nth prime is approximately n*log(n).

        Logarithmic integral of x is a pretty nice approximation for number of
        primes <= x, i.e.
        li(x) ~ pi(x)
        In fact, for the numbers we are concerned about( x<1e11 ),
        li(x) - pi(x) < 50000

        Also,
        li(x) > pi(x) can be safely assumed for the numbers which
        can be evaluated by this function.

        Here, we find the least integer m such that li(m) > n using binary search.
        Now pi(m-1) < li(m-1) <= n,

        We find pi(m - 1) using primepi function.

        Starting from m, we have to find n - pi(m-1) more primes.

        For the inputs this implementation can handle, we will have to test
        primality for at max about 10**5 numbers, to get our answer.

        References
        ==========

        - https://en.wikipedia.org/wiki/Prime_number_theorem#Table_of_.CF.80.28x.29.2C_x_.2F_log_x.2C_and_li.28x.29
        - https://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number
        - https://en.wikipedia.org/wiki/Skewes%27_number

        Examples
        ========

        >>> from sympy import prime
        >>> prime(10)
        29
        >>> prime(1)
        2
        >>> prime(100000)
        1299709

        See Also
        ========

        sympy.ntheory.primetest.isprime : Test if n is prime
        primerange : Generate all primes in a given range
        primepi : Return the number of primes less than or equal to n
    """
    n = as_int(nth)
    if n < 1:
        raise ValueError("nth must be a positive integer; prime(1) == 2")
    if n <= len(sieve._list):
        return sieve[n]

    from sympy.functions.special.error_functions import li
    from sympy.functions.elementary.exponential import log

    a = 2 # Lower bound for binary search
    b = int(n*(log(n) + log(log(n)))) # Upper bound for the search.

    while a < b:
        mid = (a + b) >> 1
        if li(mid) > n:
            b = mid
        else:
            a = mid + 1
    n_primes = primepi(a - 1)
    while n_primes < n:
        if isprime(a):
            n_primes += 1
        a += 1
    return a - 1
3 Beğeni
10

C kodları derleyicisi sayesinde doğrudan makine kodlarına dönüştürülür. Runtime’a ilişkin katmanlara ve sanal makineye ihtiyaç duymaz.

Şöyle bir benzetme yapabiliriz herhalde, iki tane koşucu var. Bunlardan birisinin üzerine 4 kat kalın giysiler giydirdik, diğerinin üstünde de neredeyse hiçbir şey yok. Bu iki koşucudan üzerinde neredeyse hiçbir şey olmayan koşucu daha hızlı koşacaktır.

Python’ın yorumlayıcısının (cpython’ın) çalışma zamanında (runtime’da) C derleyicisinin derleme zamanında analiz ettiği birçok şeyi kontrol etmesi gerekir.

3 Beğeni
11

@dildeolupbiten kodu atmış zaten. O fonksiyonun bulunduğu ntheory modülü de number theory anlamına geliyor.

>>> import sympy
>>> sum(sympy.primerange(0, 2_000_000))
142913828922
1 Beğeni