Máy tính Eulers Chức năng hoàn hảo

Question

Tôi đang cố gắng tìm một cách hiệu quả để tính toán Euler's totient function.

Điều gì sai với mã này? Nó dường như không hoạt động.

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) 

Answer 1

Đây là một cách nhanh hơn nhiều, làm việc, dựa trên mô tả này trên Wikipedia:

Vì vậy, nếu n là một số nguyên dương, sau đó φ (n) là số các số nguyên k trong phạm vi 1 ≤ k ≤ n mà gcd (n, k) = 1.

Tôi không nói đây là nhanh nhất hoặc sạch nhất, nhưng nó hoạt động.

import fractions 

def phi(n): 
    amount = 0   
    for k in range(1, n + 1): 
     if fractions.gcd(n, k) == 1: 
      amount += 1 
    return amount 

Answer 2

Dường như bạn đang cố gắng sử dụng công thức sản phẩm của Euler, nhưng bạn không tính số lượng số nguyên tố chia. Bạn đang tính số nguyên tố tương đối chính cho a.

Bên cạnh đó, kể từ ngày 1 và tôi đều số nguyên, do đó là bộ phận, trong trường hợp này bạn luôn có được 0.

Answer 3

Bạn có ba vấn đề khác nhau ...

1. y cần phải được bằng n giá trị như ban đầu, không 1
2. theo một số người đã đề cập trong các ý kiến, không sử dụng phân chia số nguyên
3. n % i == 0 is True không làm những gì bạn nghĩ vì Python chuỗi các so sánh! Ngay cả khi n % i bằng 0 thì 0 == 0 là TrueNHƯNG0 is True là False! Sử dụng parens hoặc chỉ cần thoát khỏi so sánh với True vì đó là không cần thiết anyway.

Sửa những vấn đề,

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) 

Answer 4

Liên quan đến hiệu quả, tôi đã không nhận thấy bất cứ ai đề cập đến rằng gcd (k, n) = UCLN (n-k, n). Sử dụng thực tế này có thể tiết kiệm gần một nửa công việc cần thiết cho các phương pháp liên quan đến việc sử dụng gcd. Chỉ cần bắt đầu đếm với 2 (vì 1/n và (n-1)/k sẽ luôn không thể hủy được) và thêm 2 mỗi lần gcd là một.

Answer 5

Tôi đang làm việc trên thư viện mật mã trong python và đây là những gì tôi đang sử dụng. gcd() là phương pháp của Euclid để tính ước số chung lớn nhất và phi() là hàm tổng.

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 

Answer 6

Trên thực tế để tính toán phi (bất kỳ số nói n)
Chúng tôi sử dụng Formula
trong đó p là thừa số nguyên tố của n.

Vì vậy, bạn có vài sai lầm trong mã của bạn:
1. y nên bằng n
2.Đối với 1/i thực sự là 1 và i cả hai đều là số nguyên để đánh giá của chúng cũng sẽ là số nguyên, do đó sẽ dẫn đến kết quả sai.

Đây là mã có các chỉnh sửa được yêu cầu.

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