Untitled
unknown
plain_text
5 months ago
1.2 kB
3
Indexable
#include <stdio.h> // Function to compute Euler's Totient function (phi) for a number void computeTotient(int n); int main() { char choice; do { int n; printf("Enter a positive integer: "); scanf("%d", &n); // Compute the Euler's Totient function for the entered number computeTotient(n); // Ask if the user wants to continue printf("Do you want to continue? (y/n): "); scanf(" %c", &choice); // Note the space before %c to ignore leftover newline characters } while (choice == 'y' || choice == 'Y'); // Loop while user chooses 'y' // Program completed message printf("Program completed by Nishchal Pandit\n"); return 0; } // Function to compute Euler's Totient function for an integer n void computeTotient(int n) { long long phi[n + 1]; // Initialize phi values where phi[i] = i for (int i = 1; i <= n; i++) { phi[i] = i; } // Apply the Sieve of Eratosthenes approach to calculate totient values for (int p = 2; p <= n; p++) { if (phi[p] == p) { // p is a prime number phi[p] = p - 1; for (int i = 2 * p; i <= n; i += p) { phi[i] = (phi[i] / p) * (p - 1); } } } // Print the Euler's Totient value for n printf("Totient value of %d: %lld\n", n, phi[n);
Editor is loading...
Leave a Comment