// -----------------------------------------------------------------------------
// Primes                                                                     C#
// -----------------------------------------------------------------------------

static List<int> Primes(int limit)
{
    List<int> primes = new List<int>();
    for (int k = 2; k <= limit; k++) {
        bool prime = true;
        int rk = (int)Math.Sqrt(k);
        foreach (int p in primes) {
            if (rk < p) break;
            if (k % p == 0) {
                prime = false;
                break;
            }
        }
        if (prime) primes.Add(k);
    }
    return primes;
}

// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
// Prime Factors                                                              C#
// -----------------------------------------------------------------------------

static Dictionary<int, int> PrimeFactors(int n, List<int> primes)
{
    Dictionary<int, int> factors = new Dictionary<int, int>();
    int nr = (int)Math.Sqrt(n);
    foreach (int p in primes) {
        if (n == 1 || p > nr) break;
        if (n % p == 0) {
            factors[p] = 0;
            while (n % p == 0) {
                factors[p]++;
                n /= p;
            }
        }
    }
    if (n > 1) factors[n] = 1;
    return factors;
}

// -----------------------------------------------------------------------------