39 lines
941 B
C#
39 lines
941 B
C#
using static System.Console;
|
|
using static System.Linq.Enumerable;
|
|
|
|
public class Program
|
|
{
|
|
static void Main()
|
|
{
|
|
for (int i = 1; i <= 25; i++) {
|
|
int t = Totient(i);
|
|
WriteLine(i + "\t" + t + (t == i - 1 ? "\tprime" : ""));
|
|
}
|
|
WriteLine();
|
|
for (int i = 100; i <= 100_000; i *= 10) {
|
|
WriteLine($"{Range(1, i).Count(x => Totient(x) + 1 == x):n0} primes below {i:n0}");
|
|
}
|
|
}
|
|
|
|
static int Totient(int n) {
|
|
if (n < 3) return 1;
|
|
if (n == 3) return 2;
|
|
|
|
int totient = n;
|
|
|
|
if ((n & 1) == 0) {
|
|
totient >>= 1;
|
|
while (((n >>= 1) & 1) == 0) ;
|
|
}
|
|
|
|
for (int i = 3; i * i <= n; i += 2) {
|
|
if (n % i == 0) {
|
|
totient -= totient / i;
|
|
while ((n /= i) % i == 0) ;
|
|
}
|
|
}
|
|
if (n > 1) totient -= totient / n;
|
|
return totient;
|
|
}
|
|
}
|