Sort 25 Discussions, By:
Please Login in order to post a comment
Major algorithmic hint:
I was surprised to find that all relevant chains start at very small primes. The first prime number of any chain is <= 131 (!). Knowing this you should be able to easily solve all test cases.
Note: even N=2 is a sum/chain (with only one element, though)
Is there any way to solve this without considering the fact that all such chains start with a small prime?
just for the record: under 100 million there are only 1392 records exists
anybody have solution in java
At first I felt this task is really difficult, almost unsolvable but once I found the longest possible chain starting with 2 and which is prime and less then or equal to 10**12. Then I realized this task is not that hard.
So if you feel stuck or just have no ideas. Then build an algorithm which finds the result mentioned before and I believe you will know how to continue.
sum([7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89])=953
sum([23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]) = 983
983 is also a prime number, then why the ans is 953 not 983?
The first sum has a longer chain of primes, the problem ask for the longest chain, not for the largest sum