56 lines
803 B
C
56 lines
803 B
C
#include <stdio.h>
|
|
|
|
int
|
|
totient(int n)
|
|
{
|
|
int result = n;
|
|
|
|
for (int i=2; i*i <= n; i+=2) {
|
|
if (n % i == 0) {
|
|
while (n % i == 0)
|
|
n /= i;
|
|
result -= result / i;
|
|
}
|
|
|
|
if (i == 2)
|
|
i = 1;
|
|
}
|
|
|
|
if (n > 1)
|
|
result -= result / n;
|
|
return result;
|
|
}
|
|
|
|
int
|
|
main(void)
|
|
{
|
|
int count, n, tot;
|
|
|
|
printf(" n phi prime\n");
|
|
printf("--------------\n");
|
|
|
|
count = 0;
|
|
for (n = 1; n <= 25; n++) {
|
|
tot = totient(n);
|
|
|
|
if (tot == n - 1)
|
|
count++;
|
|
|
|
printf("%2d %2d %s\n", n, tot, tot == (n-1) ? "true" : "false");
|
|
}
|
|
|
|
printf("\n");
|
|
|
|
for (n = 26; n <= 100000; n++) {
|
|
tot = totient(n);
|
|
if (tot == n-1)
|
|
count++;
|
|
|
|
if (n == 100 || n == 1000 || n == 10000) {
|
|
printf("\nNumber of primes up to %6d = %4d\n", n, count);
|
|
}
|
|
}
|
|
|
|
return 0;
|
|
}
|