OiO.lk Community platform!

Oio.lk is an excellent forum for developers, providing a wide range of resources, discussions, and support for those in the developer community. Join oio.lk today to connect with like-minded professionals, share insights, and stay updated on the latest trends and technologies in the development field.
  You need to log in or register to access the solved answers to this problem.
  • You have reached the maximum number of guest views allowed
  • Please register below to remove this limitation

special number checking froim L to R

  • Thread starter Thread starter InsiderLabs
  • Start date Start date
I

InsiderLabs

Guest
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

Code:
3
9

Output

Code:
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
<blockquote>
<p><strong>Encryption key pair</strong><br />
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. .</p>
<p>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!</p>
<p>Input:</p>
<p>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.</p>
<p>Ouput:</p>
<p>Number of strong encryption key pairs that An's group wants to know.</p>
<p>Input</p>
<pre><code>3
9
</code></pre>
<p>Output</p>
<pre><code>5
</code></pre>
<p>Explain:</p>
<p>With L = 3, R = 9: There are 5 pairs of encryption keys: (3, 5), (3, 7), (5, 6), (5, 7), (6, 7).</p>
</blockquote>
<p>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</p>
<p>My code quite slow, with big number like 100000 101000 cant check. Does anyone have a faster and more optimal solution? Thanks</p>
 
Top