MagicDiamonds
SRM 524 · 2011-05-25 · by cgy4ever
Problem Statement
The Magic Diamonds are very strange. For any positive integer x you can use Transfer Magic to transfer x Magic Diamonds at once. However, if x is a prime number, the Magic Diamonds will disappear instead of getting transferred. You are not allowed to lose any of the Magic Diamonds, therefore you may never use Transfer Magic on a prime number of Magic Diamonds. Your task is to transfer all Magic Diamonds using Transfer Magic as few times as possible.
You are given a
Notes
- A positive integer x is a prime number if and only if it has exactly 2 divisors: 1 and x. Note that 1 is not a prime number.
- Your task can always be accomplished. For example, you can use Transfer Magic n times and transfer 1 Magic Diamond each time.
Constraints
- n will be between 1 and 1,000,000,000,000 (10^12), inclusive.
Statement by TopCoder, Inc. — view the original on the archive.
2 Returns: 2
We have to use Transfer Magic twice, each time we transfer 1 Magic Diamond.
4294967297 Returns: 1
We just need to use Transfer Magic once, because 4294967297 is not a prime. We have 4294967297 = 641 * 6700417.
2147483647 Returns: 2
This time n is a prime, so we have to use Transfer Magic at least twice. We have 2147483647 = 2147400000 + 83647 (83647 = 233 * 359, which is not a prime), thus the answer is 2.
1 Returns: 1
8566 Returns: 1
Submissions are judged against all 116 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MagicDiamonds with a public method long long minimalTransfer(long long n) · 116 test cases · 2 s / 256 MB per case