首頁>Program>source

我正在尝試實現 primeFac()函式 將正整數 n作為輸入 並返迴包含 n素數分解中所有數字的列表

我已经走了這麼远,但是我认為最好在這裏使用遞迴,不確定在這裏如何建立遞迴代碼,基本情况是什麼? 首先。

我的代碼:

def primes(n):
    primfac = []
    d = 2
    while (n > 1):
         if n%d==0:
             primfac.append(d)
    # how do I continue from here... ?
最新回復
  • 1月前
    1 #

    一个簡單的試驗部門:

    def primes(n):
        primfac = []
        d = 2
        while d*d <= n:
            while (n % d) == 0:
                primfac.append(d)  # supposing you want multiple factors repeated
                n //= d
            d += 1
        if n > 1:
           primfac.append(n)
        return primfac
    

    O(sqrt(n)) 複雜性(最壞的情况).您可以通過特殊外壳2並仅在奇數 d上迴圈来轻松改进它 (或使用特殊大小寫的小質數,並迴圈使用较少的除數)。

  • 1月前
    2 #

    這是一个基於理解的解決方案,它可能是您可以在Python中使用的最接近遞迴解決方案的方法 大量。

    您可以使用一行获得適当的除數:

    divisors = [ d for d in xrange(2,int(math.sqrt(n))) if n % d == 0 ]
    

    然後我们可以測試除數中的數字是否為質數:

    def isprime(d): return all( d % od != 0 for od in divisors if od != d )
    

    測試其他除數是否除以d。

    然後我们可以過濾素數除數:

    prime_divisors = [ d for d in divisors if isprime(d) ]
    

    当然,它可以組合成一个函式:

    def primes(n):
        divisors = [ d for d in range(2,n//2+1) if n % d == 0 ]
        return [ d for d in divisors if \
                 all( d % od != 0 for od in divisors if od != d ) ]
    

    在這裏,\可以在不打斷Python縮排的情况下打破界限。

  • 1月前
    3 #

    primefac模組使用了數个世纪以来數學家開發的所有精美技術进行分解:

    #!python
    import primefac
    import sys
    n = int( sys.argv[1] )
    factors = list( primefac.primefac(n) )
    print '\n'.join(map(str, factors))
    

  • 1月前
    4 #

    這是我通過試驗除法进行因式分解的版本,它結合了仅除以2和Daniel Fischer提出的奇數整數的優化方法:

    def factors(n):
        f, fs = 3, []
        while n % 2 == 0:
            fs.append(2)
            n /= 2
        while f * f <= n:
            while n % f == 0:
                fs.append(f)
                n /= f
            f += 2
        if n > 1: fs.append(n)
        return fs
    

    將試驗除以2和奇數的改进是wheel因數分解,它使用了一組潜在質數之間的間隔缺口来大大减少了試驗的划分次數.在這裏,我们使用2、3、5轮:

    def factors(n):
        gaps = [1,2,2,4,2,4,2,4,6,2,6]
        length, cycle = 11, 3
        f, fs, nxt = 2, [], 0
        while f * f <= n:
            while n % f == 0:
                fs.append(f)
                n /= f
            f += gaps[nxt]
            nxt += 1
            if nxt == length:
                nxt = cycle
        if n > 1: fs.append(n)
        return fs
    

    因此, print factors(13290059) 將輸出 [3119, 4261] .分解因子轮的O(sqrt(n))時間複雜度与普通試驗除法一樣,但是在實践中会快两倍或三倍。

    我在博客上做了很多有關質數的工作.請隨時訪問和學習.

  • 1月前
    5 #

    大多數上述解決方案似乎都不完整.素數分解將重複數 (e.g. 9 = [3 3])的每个素數 .

    此外,為了實現方便,上述解決方案可以寫為惰性函式.

    使用 sieve Of Eratosthenes 找到要測試的素數是最佳的,但是; 上面的實現使用了不必要的記憶體.

    我不確定是否/如何 對於n的除法檢驗將優於仅應用素因數。

    虽然這些解決方案確實有帮助,但我建議以下 "wheel factorization"

    two functions -

    Function-1 :
    

    def primes(n): if n < 2: return yield 2 plist = [2] for i in range(3,n): test = True for j in plist: if j>n**0.5: break if i%j==0: test = False break if test: plist.append(i) yield i

    Function-2 :
    
    def pfactors(n): for p in primes(n): while n%p==0: yield p n=n//p if n==1: return list(pfactors(99999)) [3, 3, 41, 271] 3*3*41*271 99999 list(pfactors(13290059)) [3119, 4261] 3119*4261 13290059

  • printing:从瀏覽器直接print而無需print弹出視窗
  • datetime:Python老化時間,第2部分:時區