Almost Prime
Time limit2sMemory limit256 MB
Count integers of the form p^N (p prime, N greater than or equal to 2) that fall within a range [A, B] with B up to 10^14.
- Level
Medium6 of 10
- Topics
- Number theory, Math, Binary search
- Solved
- No attempts yet
Problem
A number is called an almost prime if it can be written as p^N, where p is a prime number and N is an integer with N >= 2.
Given two integers A and B, count how many almost primes are greater than or equal to A and less than or equal to B.
Input
The first line contains two integers A and B, separated by a space.
Output
Print the number of almost primes in the given range.
Constraints
- 1 <= A <= B <= 10^14