قسمة متكررة

القسمة المتكررة (بالإنجليزية: Trial division)‏ هي الخوارزمية الأكثر صعوبة من أجل تفكيكك عدد ما إلى جداء أعداد أولية ولكنها أسهل خوارزمية من حيث الفهم.[1]

الطريقة

def trial_division(n):
    """Return a list of the prime factors for a natural number."""
    if n <2: return []
    primes = prime_sieve(int(n**0.5) + 1)
    prime_factors = []

    for p in primes:
        if p*p> n: break
        while n % p == 0:
            prime_factors.append(p)
            n //= p
    if n> 1: prime_factors.append(n)

    return prime_factors

السرعة

\pi (2^{n/2})\approx {2^{n/2} \over \left({\frac {n}{2}}\right)\ln 2}

حيث $\scriptstyle \pi (x)$ هي الدالة المعدة للأعداد الأولية الأصغر من x.

مراجع

"معلومات عن قسمة متكررة على موقع mathworld.wolfram.com". mathworld.wolfram.com. مؤرشف من الأصل في 22 أكتوبر 2018. الوسيط |CitationClass= تم تجاهله (مساعدة)

وصلات خارجية

بوابة خوارزميات
بوابة علم الحاسوب
بوابة نظرية الأعداد

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] "معلومات عن قسمة متكررة على موقع mathworld.wolfram.com". mathworld.wolfram.com. مؤرشف من الأصل في 22 أكتوبر 2018. الوسيط |CitationClass= تم تجاهله (مساعدة)