Number of private keys (cryptography)?

Question

Cryptography

Good afternoon!
There is a programming problem:
The private key is given as (p,q)
It is necessary to determine the number of suitable public keys.
I can't think of an algorithm

Answer 1

We decompose the GCD and LCM into prime factors.
For each prime, we define the degree in gcd and lcm.
If for at least one simple ap[GCD,a] > p[LCM,a], STOP: 0.
[EXAMPLE: GCD=2, LCM=5 — well, that doesn't happen, does it? And it does not happen because in GCD 2¹, and in LCM 2 ⁰ .]
Now let's take another example: in GCD 2¹, in LCM 2³. This means that in one number there will be 2¹, in the other 2³ - two options.
Total answer: 0 if at least one prime a has p[LCM,a] < p[gcd,a]
Otherwise 2^{NUMBER{prime a} ( p[LCM,a] > p[gcd,a] ) }
EXAMPLE: GCD = 2¹ 3 ⁰ 5² = 50, LCM = 2³ 3¹ 5² = 600
1-2. 1-0-2 = 50, 3-1-2 = 600 and 600-50
3-4. 1-1-2 = 150, 3-0-2 = 200 and 200-150
Right, four pieces?
UPD. For greater speed, you can parse LCM into prime factors, and in GCD you can simply check what happened: is there a higher degree, are there extraneous primes.
And, of course, very extreme cases: GCD = LCM → 1 piece, GCD> LCM → 0 pieces