Valid Key Count

Problem Statement

Valid Key Count Problem Description A security team has found a new encryption scheme. A number is a valid key when it has exactly three positive divisors. For instance, 4 is a valid key, because its divisors are 1, 2 and 4; 6 is not, because its divisors are 1, 2, 3 and 6. You are given an array keys of length n . For every index i with 0 <= i < n , report how many valid keys lie in the range [1, keys[i]] , both ends included. Complete the function getValidKeyCount , which takes the array keys and returns one count per query, in the same order. Note: A is a divisor of B when some integer C satisfies A * C = B . Only positive divisors are counted. Input Format The first line contains an integer n , the number of elements in keys . Each of the next n lines contains one integer keys[i] . Output Format Print n lines; line i is the number of valid keys in [1, keys[i]] . Constraints 1 <= n <= 2000 (inferred -- the paper says n <= 10^5; lowered so that one output stays under t