Editorial for ECOO '12 R2 P1 - Prime Time


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Every number is a product of two numbers: The message code number in the range 0 to 3030, and the prime number key in the range 100\,000 to 500\,000. The easiest thing to do is simply search one of the message numbers sequentially for the first factor you find starting at 100\,000.

It may also be possible in some cases to find the GCF (greatest common factor) of two of the message numbers using the Euclidean algorithm or some other method. But this method may not find the right key. For example, if the two message numbers you select are both even, the GCF will actually be double the key.


Comments

There are no comments at the moment.