Facebook Hacker Cup 2015 Round 1, Homework

Problem Statement:

https://www.facebook.com/hackercup/problem/582396081891255/

Solution:

First we generate the list of prime numbers between 2 and 10^7.
Then we calculate the primacity of each number between 2 and 10^7 and save the results into an array.
To calculate the primacity of all numbers, we set all primacities to zero, then for each prime number we increase the primacity of each multiple of that prime by 1.
At the end we will have the primacity of all numbers completely filled, and it will be easy to count the requested answer.

Example codes in C#:

            int T = inp.NextInt ( );
            List<int> primes = GetPrimes ( 10000000 );

            int[] prmCity = new int[10000001];
            for ( int i = 0; i < primes.Count; i++ )
            {
                int p = primes[i];
                for ( int pp = p; pp < prmCity.Length; pp+=p )
                {
                    prmCity[pp] += 1;
                }
            }

            for ( int t = 0; t < T; t++ )
            {
                int A = inp.NextInt ( );
                int B = inp.NextInt ( );
                int K = inp.NextInt ( );

                int cnt=0;
                for ( int i = A; i <= B; i++ )
                {
                    if ( prmCity[i] == K )
                        cnt++;
                }

                int ans=cnt;
                Console.WriteLine ( "Case #{0}: {1}", t + 1, ans );
            }


        private static List<int> GetPrimes ( int maxPrimeNumber )
        {
            bool[] isPrime = GetIsPrime ( maxPrimeNumber );
            List<int> primes = new List<int> ( );
            for ( int i = 2; i < isPrime.Length; i++ )
            {
                if ( isPrime[i] )
                    primes.Add ( i );
            }
            return primes;
        }

        private static bool[] GetIsPrime ( int max )
        {
            // Sieve of Eratosthenes
            bool[] isPrime = new bool[max + 1];
            for ( int i = 0; i <= max; i++ )
                isPrime[i] = true;
            isPrime[0] = false;
            isPrime[1] = false;
            for ( int x = 2; x * x <= max; x++ )
            {
                if ( isPrime[x] )
                {
                    int xx = x;
                    while ( true )
                    {
                        xx += x;
                        if ( xx <= max )
                            isPrime[xx] = false;
                        else
                            break;
                    }
                }
            }
            return isPrime;
        }