Untitled

 avatar
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