Body: I am solving this problem:1474B - Different Divisors
We need to find the smallest integer a such that:
a has at least 4 divisors the difference between any two divisors of a is at least d
My idea is to construct a as:
a = p⋅q
where:
p is the smallest prime such that p≥d+1 q is the smallest prime such that q≥p+d
Then I output a=p⋅q. 373450651
This works for all samples I tested, but I am not fully sure about correctness for all d. Can someone confirm if this construction is always optimal, or provide a counterexample if it fails?
Auto comment: topic has been updated by Mohammed_Hamed8 (previous revision, new revision, compare).
Yeah, it's correct because:
$$$a = p * q$$$ has exactly $$$4$$$ divisors, which are $$$1, p, q, p * q$$$
$$$p - 1 ≥ d$$$, $$$q - p ≥ d$$$, and $$$p * q - q = (p - 1) * q$$$. Because $$$p - 1 ≥ d$$$ so $$$(p - 1) * q ≥ d$$$
p*q won't always be the smallest, there are cases where p*p*p might be the smallest ig, or, just to be safe?
I will try finding test cases for it
oh never mind, q will surely be smaller than p*p..