Encryption key pair An is working in a large company and is responsible for securing important company data. To ensure data security for the company, An joined the team to develop an asymmetric encryption system by creating encryption key pairs based on "special" numbers that An's team had just discovered. A “special” number is a positive integer that cannot be divided by the square of any integer greater than 1. The complexity of these “special” numbers is well suited for creating strong encryption keys. .
Now, An's group wants to know how many pairs of strong encryption keys there are, with each key falling within a certain integer range from L to R. An encryption key pair (x, y) is considered strong if both key x, The key y and the value x*y are both "special" numbers, plus x must always be less than y. An was mainly responsible for writing the program to calculate the number of strong key pairs, but unfortunately he forgot most of the programming. Please help An write this program!
Input:
A line contains two positive integers L and R (1 ≤ L < R ≤ 10^9 , R − L ≤ 1000 ) are two limits of the range of values of the encryption keys.
Ouput:
Number of strong encryption key pairs that An's group wants to know.
Input
3
9
Output
5
Explain:
With L = 3, R = 9: There are 5 pairs of encryption keys: (3, 5), (3, 7), (5, 6), (5, 7), (6, 7).
My solution is to find the prime factors of each number. If there are duplicate factors like the number 4 is 2^2, print false, if true, then compare them together, if the factors of the two numbers are the same. then false, otherwise true
My code quite slow, with big number like 100000 101000 cant check. Does anyone have a faster and more optimal solution? Thanks