[Codility] Lesson11. CountSemiprimes (C#)

문제: app.codility.com/programmers/lessons/11-sieve_of_eratosthenes/count_semiprimes/

CountSemiprimes coding task - Learn to Code - Codility

 

아.. 문제 이해도 어렵다.

 

            int[] result = new int[P.Length];
            int[] primeCheck = new int[N + 1];
            int[] presum = new int[N + 1];

            primeCheck[0] = 1;
            primeCheck[1] = 1;
            for (int i = 2; i * i <= N; i++)
            {
                if (primeCheck[i] == 1) continue;

                int k = i * i;
                while (k <= N)
                {
                    primeCheck[k] = 1;
                    k += i;
                }
            }

            for (int i = 2; i * i <= N; i++)
            {
                if (primeCheck[i] == 1) continue;

                int k = i * i;
                while (k <= N)
                {
                    if (primeCheck[i] == 0 && primeCheck[k / i] == 0)
                        primeCheck[k] = 2;
                    k += i;
                }
            }

            int count = 0;
            for (int i = 0; i <= N; i++)
            {
                if (primeCheck[i] == 2)
                    count++;
                presum[i] = count;
            }

            for (int i = 0; i < P.Length; i++)
            {
                result[i] = presum[Q[i]] - presum[P[i] - 1];
            }

            return result;