Problem in BEAUTIFUL PRIMES (hackerearth)

I have been trying to solve this question: https://www.hackerearth.com/practice/math/number-theory/basic-number-theory-1/practice-problems/algorithm/beautiful-primes/description/

I cant even understand its editorial…
Any clue as to how to solve the problem would be of great help…!!!

The tutorial says that for a given prime no. P it’s s ( P) i.e. the sum of all it’s divisors is P (as prime no. Is divisible by only itself)
So S(P^2) = P+P^2
Let’s take an example let p=7
So S(7) = 7 as 7 is a prime no.
S(49)=S(7^2) = 7+49
As there are only two divisors of 49 , that are 7 and 49 itself
So S(P^a)=P+P^2+P^3 and so on till P^a
So the answer will be S(P1^a1)S(P2^a2) and so on for n prime no.
Now the let’s take an example in given sample test case of question
So S(2^2) = 2+4=6
S(3^1)=3
S(5^1)=5
So answer is (6
3*5)=90 which is the answer
Just a last elaboration:
For the question you have to find the sum of all no. With prime factor’s power starting with 1
So answer would be (2^2+2^1) * 3 * 5 for sample test case
Hope it helps you :blush:

1 Like

It’s 6 * 3 * 5

Thanks Man… :slight_smile:

1 Like