Calcolo Eulers Totient Funzione

Sto cercando di trovare un modo efficiente per calcolare Eulero totient funzione.

Cosa c’è di sbagliato con questo codice? Non sembra essere funzionante.

def isPrime(a):
    return not ( a < 2 or any(a % i == 0 for i in range(2, int(a ** 0.5) + 1)))

def phi(n):
    y = 1
    for i in range(2,n+1):
        if isPrime(i) is True and n % i  == 0 is True:
            y = y * (1 - 1/i)
        else:
            continue
    return int(y)
  • 1/i non fare ciò che si pensa si può provare.
  • utilizzare python3 invece di python2 🙂
  • O mettere from __future__ import division alla parte superiore del vostro codice per attivare il galleggiante divisione in Python 2.
  • Progetto Eulero eh? Mi piacerebbe compilare un elenco di numeri primi, in anticipo, o almeno cache quelli che hai trovato.
InformationsquelleAutor Brock West | 2013-08-07

 

7 Replies
  1. 23

    Qui è molto più veloce, modo di lavorare, sulla base di questa descrizione su Wikipedia:

    Quindi se n è un intero positivo, allora φ(n) è il numero di interi k nell’intervallo 1 ≤ k ≤ n per cui gcd(n, k) = 1.

    Non sto dicendo che questo è il più veloce o il più pulito, ma funziona.

    import fractions
    
    def phi(n):
        amount = 0        
        for k in range(1, n + 1):
            if fractions.gcd(n, k) == 1:
                amount += 1
        return amount
    • Forse cercavi range(1, n+1)?
    • Sì, grazie.
    • Queste proprietà, è particolarmente utile Se p è un numero primo, ϕ(p)=p−1 gcd(p,q)=1where 1<=d<p Se p è un numero primo e k>0, ϕ(p^k)=p^k−p^(k−1) Se a e b sono relativamente primi, ϕ(ab)=ϕ(a).ϕ(b) e-maxx-eng.github.io/algebra/phi-function.html
    • Beh, stavo cercando un modo per calcolare $\phi(10^{200})$ (phi(10**200))…
  2. 5

    Si hanno tre diversi problemi…

    1. y deve essere uguale a n come valore iniziale, non 1
    2. Come alcuni hanno detto nei commenti, non utilizzare la divisione di interi
    3. n % i == 0 is True non è fare ciò che si pensa a causa di Python concatenamento i paragoni! Anche se n % i è uguale a 0 poi 0 == 0 è True MA 0 is True è False! L’uso delle parentesi o semplicemente sbarazzarsi di confronto per True dal momento che non è necessario in ogni caso.

    Fissazione di tali problemi,

    def phi(n):
        y = n
        for i in range(2,n+1):
            if isPrime(i) and n % i == 0:
                y *= 1 - 1.0/i
        return int(y)
  3. 3

    Sto lavorando su una libreria di crittografia in python e questo è quello che sto usando. gcd() è Euclide metodo per il calcolo del massimo comune divisore, e phi() è il totient funzione.

    def gcd(a, b):
        while b:
            a, b=b, a%b
        return a
    def phi(a):
        b=a-1
        c=0
        while b:
            if not gcd(a,b)-1:
                c+=1
            b-=1
        return c
  4. 2

    Sembra che si sta tentando di utilizzare Eulero prodotto formula, ma tu non sei il calcolo del numero di numeri primi che dividono un. Si calcola il numero di elementi relativamente prime per l’a.

    Inoltre, a partire dal 1 e io sono entrambi interi, quindi, è la divisione, in questo caso si ottiene sempre 0.

  5. 2

    Per quanto riguarda l’efficienza, non ho notato nessuno contare che mcd(k,n)=mcd(n-k,n). L’utilizzo di questo fatto si possono risparmiare circa la metà del lavoro necessario per i metodi che prevedono l’uso del gcd. Basta avviare il conteggio con 2 (perché 1/n (n-1)/k sarà sempre irriducibile) e aggiungere 2 ogni volta che il gcd è uno.

    • Non stai considerando il lavoro necessario per calcolare il lavoro necessario per confrontare n con 2*k, così come il lavoro necessario per sottrarre n-k.
  6. 1

    In realtà, per calcolare phi(qualsiasi numero di dire n)

    Usiamo il Formula

    dove p sono i fattori primi di n.

    Così, hai qualche errore nel codice:

    1.y deve essere uguale a n

    2. Per 1/i effettivamente 1 e i entrambi interi, in modo che la loro valutazione sarà anche un numero intero,quindi portare a risultati errati.

    Qui è il codice con le correzioni necessarie.

    def phi(n): 
    y = n 
    for i in range(2,n+1): 
    se isPrime(i) e n % i == 0 : 
    y= y/i 
    altro: 
    continua 
    di ritorno int(y) 
    
  7. 1

    Calcolo del mcd per ogni paio di scarpe in gamma non è efficiente e non scale. Non c’è bisogno di scorrere attraverso tutta la gamma, se n non è un numero primo, è possibile controllare i fattori primi fino alla sua radice quadrata, fare riferimento a https://stackoverflow.com/a/5811176/3393095.
    Dobbiamo quindi aggiornare phi per ogni primo di phi = phi*(1 – 1/prime).

    def totatives(n):
        phi = int(n > 1 and n)
        for p in range(2, int(n ** .5) + 1):
            if not n % p:
                phi -= phi // p
                while not n % p:
                    n //= p
        #if n is > 1 it means it is prime
        if n > 1: phi -= phi // n 
        return phi
    • Questo può essere fatto molto più veloce rielaborazione loop, così ferma alla radice quadrata della corrente n valore piuttosto che l’iniziale n valore.
    • Almeno si batte esplicita test di primalità e mcd polinomi di tutte le altre esistenti risposte però.

Lascia un commento