MagicDiamonds
SRM 524 · 2011-05-25 · by cgy4ever
SRM 524 · 2011-05-25 · by cgy4ever · Advanced Math
Problem Statement
Problem Statement
You found n Magic Diamonds in the mountain. You are now thinking about transfering them to your home.
The only way you can transfer Magic Diamonds is to use Transfer Magic one or more times.
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 along n. Return the minimal number of Transfer Magic usages you need to transfer n Magic Diamonds.
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.
Examples
0)
2 Returns: 2
We have to use Transfer Magic twice, each time we transfer 1 Magic Diamond.
1)
4294967297 Returns: 1
We just need to use Transfer Magic once, because 4294967297 is not a prime. We have 4294967297 = 641 * 6700417.
2)
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.
3)
1 Returns: 1
4)
8566 Returns: 1
Submissions are judged against all 116 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
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