Computing Eulers Totient Function

Question

Я пытаюсь найти эффективный способ вычисления Euler's totient function.

Что не так с этим кодом? Кажется, он не работает.

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

Вот гораздо быстрее, работая путь, основанный на этом описании в Википедии:

Таким образом, если п целое положительное число, то φ (п) количество целых чисел к в диапазон 1 ≤ k ≤ n, для которого gcd (n, k) = 1.

Я не говорю, что это самый быстрый или чистый, но он работает.

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

Похоже, вы пытаетесь использовать формулу произведения Эйлера, но вы не вычисляя число простых чисел, которые делят. Вы вычисляете число элементов, взаимно простых с а.

Кроме того, с 1 и я оба целые числа, так это разделение, в этом случае вы всегда получите 0.

Answer 3

У вас есть три проблемы ...

1. y должно быть равно n в качестве исходного значения, а не 1
2. Как некоторые уже упоминалось в комментариях, не используйте целочисленное деление
3. n % i == 0 is True не делать то, что вы думаете, из-за Python связывая сравнения! Даже если n % i равно 0, то 0 == 0 является TrueНО НО0 is True является False! Используйте parens или просто избавляйтесь от True, так как это не обязательно.

Закрепление этих проблем,

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

Что касается эффективности, я не заметил, кто отметить, что НОД (к, п) = НОД (п-к, п). Используя этот факт, можно сэкономить примерно половину работы, необходимой для методов, связанных с использованием gcd. Просто запустите счет с 2 (потому что 1/n и (n-1)/k всегда будут неприводимы) и добавьте 2 каждый раз, когда gcd является одним.

Answer 5

Я работаю над криптографической библиотекой в ​​python, и это то, что я использую. gcd() - метод Евклида для вычисления наибольшего общего делителя, а phi() - функция-функция.

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

На самом деле для расчета фиты (любое число говорит, п)
Мы используем Formula
где р являются простыми множителями п.

Итак, у вас есть несколько ошибок в коде:
1. y должен быть равен n
2.Для 1/i фактически 1 и i оба являются целыми числами, поэтому их оценка также будет целым числом, что приведет к неправильным результатам.

Вот код с необходимыми исправлениями.

 
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)