Two divisors | Practice Problems

Two divisors

★★★★★

1.8

4 votes

dynamic programming, algorithms, medium, Dynamic Programming

Details

Submissions

Discussion

Editorial

Problem

You are given an integer $N$ . You have to find how many numbers ( $X$ ) exist for the given $N$ such that $1 \le x \le N$ and the number of divisors of $X$ is a power of $2$ .

Input format

First line: $Q$ (number of queries)
Next line: $Q$ space-separated integer such that the $i^{th}$ integer is $N$ for the $i^{th}$ query

Output format
Print a single integer denoting the number of valid $1 \le x \le N$ for each query as space-separated integers.

Constraints

$1 \le Q \le 10^6$
$1 \le N \le 10^6$

Time Limit: 2

Memory Limit: 256

Source Limit:

Explanation

For $N=3$

Number of divisors of $1 = 1$ (can be represented as $2^0$ )

Number of divisors of $2 = 2$ (can be represented as $2^1$ )

Number of divisors of $3 = 2$ (can be represented as $2^1$ )

Therefore, the total count of valid $x (1 \le x \le 3)$ is $3$ .