fork download 
  1. import math
  2.  
  3. # Function to compute the Euler's totient function for each number up to n
  4. def compute_totient(n):
  5.     phi = [i for i in range(n + 1)]
  6.  
  7.     for i in range(2, n + 1):
  8.         if phi[i] == i:  # Check if i is prime
  9.             for j in range(i, n + 1, i):
  10.                 phi[j] = phi[j] // i * (i - 1)
  11.  
  12.     return phi
  13.  
  14. # Function to find and display numbers that are relatively prime to each number up to n
  15. def display_relatively_prime_numbers(n, phi):
  16.     for i in range(1, n + 1):
  17.         relatively_prime_numbers = [j for j in range(1, i) if math.gcd(i, j) == 1]
  18.         print(f"phi({i}) = {phi[i]}: Relatively prime numbers are: {relatively_prime_numbers}")
  19.  
  20. def main():
  21.     n = int(input("Enter the value of n: "))
  22.  
  23.     phi = compute_totient(n)
  24.  
  25.     display_relatively_prime_numbers(n, phi)
  26.  
  27. if __name__ == "__main__":
  28.     main()
Success #stdin #stdout 0.04s 9844KB
comments ()
stdin 
20
stdout 
Enter the value of n: phi(1) = 1: Relatively prime numbers are: []
phi(2) = 1: Relatively prime numbers are: [1]
phi(3) = 2: Relatively prime numbers are: [1, 2]
phi(4) = 2: Relatively prime numbers are: [1, 3]
phi(5) = 4: Relatively prime numbers are: [1, 2, 3, 4]
phi(6) = 2: Relatively prime numbers are: [1, 5]
phi(7) = 6: Relatively prime numbers are: [1, 2, 3, 4, 5, 6]
phi(8) = 4: Relatively prime numbers are: [1, 3, 5, 7]
phi(9) = 6: Relatively prime numbers are: [1, 2, 4, 5, 7, 8]
phi(10) = 4: Relatively prime numbers are: [1, 3, 7, 9]
phi(11) = 10: Relatively prime numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
phi(12) = 4: Relatively prime numbers are: [1, 5, 7, 11]
phi(13) = 12: Relatively prime numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
phi(14) = 6: Relatively prime numbers are: [1, 3, 5, 9, 11, 13]
phi(15) = 8: Relatively prime numbers are: [1, 2, 4, 7, 8, 11, 13, 14]
phi(16) = 8: Relatively prime numbers are: [1, 3, 5, 7, 9, 11, 13, 15]
phi(17) = 16: Relatively prime numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
phi(18) = 6: Relatively prime numbers are: [1, 5, 7, 11, 13, 17]
phi(19) = 18: Relatively prime numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
phi(20) = 8: Relatively prime numbers are: [1, 3, 7, 9, 11, 13, 17, 19]
https://ideone.com/0mdVZX
Euler's Totient. Display Coprimes and Totient
language:
Python 3 (python  3.12)
created:
103 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!