A deep-space relay network extends a starship's communication range by chaining together signal beacons. Each beacon design carries a whole-number power rating, and only designs whose rating is a prime number are certified for use on the relay — anything else causes interference and is rejected. Mission control has certified every prime-rated design with a power rating from 2 up to a maximum n (inclusive), and once certified, a design may be installed on the relay any number of times.
Given a required total signal strength target, determine the minimum number of beacons (drawing freely and repeatedly from the certified prime power ratings) whose ratings sum to exactly target. If no combination of certified beacons can reach target exactly, report that it is impossible.
A single line containing two space-separated integers n and target.
A single integer: the minimum number of beacons needed so their power ratings sum to exactly target, or -1 if it cannot be done.
Example 1
Input
10 10
Expected
2
Explanation
The certified prime power ratings up to 10 are 2, 3, 5, 7. No single certified beacon has rating 10, but two beacons can: 5+5=10 (or 3+7=10). So the minimum number of beacons is 2.
Example 2
Input
5 11
Expected
3
Explanation
The certified prime power ratings up to 5 are 2, 3, 5. Checking every pair (2+2=4, 2+3=5, 2+5=7, 3+3=6, 3+5=8, 5+5=10) shows no two beacons reach 11. Reusing 3 three times: 3+3+5=11 works with 3 beacons, and no 2-beacon combination reaches 11, so the minimum is 3.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →