85 lines
3.1 KiB
C#
85 lines
3.1 KiB
C#
|
using System;
|
|||
|
|
|
|||
|
|
namespace MobiusDemo
|
|||
|
|
{
|
|||
|
|
class Program
|
|||
|
|
{
|
|||
|
|
// -----------------------------------------------------------------
|
|||
|
|
// Settings that are identical to the Java version
|
|||
|
|
// -----------------------------------------------------------------
|
|||
|
|
private const int MU_MAX = 1_000_000; // same upper bound
|
|||
|
|
private static int[] MU = null; // will hold the sieve
|
|||
|
|
|
|||
|
|
static void Main(string[] args)
|
|||
|
|
{
|
|||
|
|
Console.WriteLine("First 199 terms of the möbius function are as follows:");
|
|||
|
|
Console.Write(" ");
|
|||
|
|
|
|||
|
|
for (int n = 1; n < 200; n++)
|
|||
|
|
{
|
|||
|
|
Console.Write($"{MobiusFunction(n),2} ");
|
|||
|
|
|
|||
|
|
// line‑break after every 20 numbers – exactly like the Java code
|
|||
|
|
if ((n + 1) % 20 == 0)
|
|||
|
|
Console.WriteLine();
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// -----------------------------------------------------------------
|
|||
|
|
// Compute μ(n) using the same sieve algorithm that the Java code
|
|||
|
|
// uses. The first call builds the whole table up to MU_MAX.
|
|||
|
|
// -----------------------------------------------------------------
|
|||
|
|
private static int MobiusFunction(int n)
|
|||
|
|
{
|
|||
|
|
// If the sieve has already been built we can return the answer
|
|||
|
|
// straight away.
|
|||
|
|
if (MU != null)
|
|||
|
|
return MU[n];
|
|||
|
|
|
|||
|
|
// -------------------------------------------------------------
|
|||
|
|
// Build the sieve (once)
|
|||
|
|
// -------------------------------------------------------------
|
|||
|
|
MU = new int[MU_MAX + 1];
|
|||
|
|
|
|||
|
|
// initialise every entry with 1 – Java did this explicitly
|
|||
|
|
for (int i = 0; i <= MU_MAX; i++)
|
|||
|
|
MU[i] = 1;
|
|||
|
|
|
|||
|
|
int sqrt = (int)Math.Sqrt(MU_MAX);
|
|||
|
|
|
|||
|
|
// first pass: multiply by -p for each prime factor p,
|
|||
|
|
// and mark multiples of p² as zero.
|
|||
|
|
for (int i = 2; i <= sqrt; i++)
|
|||
|
|
{
|
|||
|
|
if (MU[i] == 1) // i is still “prime”
|
|||
|
|
{
|
|||
|
|
// flip the sign for every multiple of i
|
|||
|
|
for (int j = i; j <= MU_MAX; j += i)
|
|||
|
|
MU[j] *= -i;
|
|||
|
|
|
|||
|
|
// any number that contains i² gets value 0
|
|||
|
|
int i2 = i * i;
|
|||
|
|
for (int j = i2; j <= MU_MAX; j += i2)
|
|||
|
|
MU[j] = 0;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// second pass: reduce the encoded values to the final μ(n)
|
|||
|
|
for (int i = 2; i <= MU_MAX; i++)
|
|||
|
|
{
|
|||
|
|
if (MU[i] == i) // only +i => μ = +1
|
|||
|
|
MU[i] = 1;
|
|||
|
|
else if (MU[i] == -i) // only -i => μ = -1
|
|||
|
|
MU[i] = -1;
|
|||
|
|
else if (MU[i] < 0) // product of an odd number of distinct primes
|
|||
|
|
MU[i] = 1;
|
|||
|
|
else if (MU[i] > 0) // product of an even number of distinct primes
|
|||
|
|
MU[i] = -1;
|
|||
|
|
// note: MU[i] == 0 stays 0 (square factor present)
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
return MU[n];
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
}
|