Sieve.txt
using TestingStuff;
namespace Helping
{
public static class Sieve
{
public static int Max;
public static List<long> Primes = null!;
public static long[] Factors = null!;
static Sieve()
{
Init(200_000);
}
private static void Init(int max)
{
Max = max + 10;
Factors = new long[Max];
Primes = new(Max);
for (long i = 2; i < Max; i++)
{
if (Factors[i] == 0)
{
Factors[i] = i;
Primes.Add(i);
}
foreach (long p in Primes)
{
if (p > Factors[i] || i * p >= Max)
break;
Factors[i * p] = p;
}
}
}
public static bool IsPrime(long num)
{
if (num < Factors.Length)
return Factors[num] != 0 && Factors[num] == num;
foreach (long p in Primes)
{
if (num % p == 0)
return false;
}
return true;
}
public static Dictionary<long, long> Factorize(long num)
{
Dictionary<long, long> ret = new(10);
foreach (long p in Primes)
{
if (num < Factors.Length)
break;
while (num % p == 0)
{
num /= p;
ret[p] = ret.GetOrAdd(p, 0) + 1;
}
}
if (num >= Factors.Length)
{
ret[num] = 1;
num = 1;
}
while (num > 1)
{
long p = Factors[num];
ret[p] = ret.GetOrAdd(p, 0) + 1;
num /= p;
}
return ret;
}
public static List<long> GetDivisorsNotSorted(long num)
{
List<long> res = new(1500) { 1 };
foreach (var prime in Factorize(num))
{
int oldN = res.Count;
for (int j = 0; j < prime.Value; j++)
{
long acc = 1;
for (int i = 0; i < oldN; i++)
{
acc *= prime.Key;
res.Add(res[i] * acc);
}
}
}
return res;
}
public static long Euler(long num)
{
if (num == 1)
return 0;
var factorise = Factorize(num);
long answ = num;
foreach (var item in factorise)
{
answ -= answ / item.Key;
}
return answ;
}
}
}