Discussion @ 2102. Michael and Cryptography @ Timus Online Judge

TLE22

Posted by Kogut.Ivan 20 Nov 2016 14:02

I get TLE on 22 test. What can you advise?

Re: TLE22

Posted by Felix_Mate 20 Nov 2016 21:22

1)In solution you must find all primes <= 10^7.
2)You must use that n<=10^18.

Re: TLE22

Posted by esbybb 21 Nov 2016 08:57

1. find all primes up to 2 millions
2. if remainder > 2 millions, check if it is a prime

Re: TLE22

Posted by esbybb 21 Nov 2016 08:57

remaining typo

Re: TLE22

Posted by Kogut.Ivan 21 Nov 2016 21:40

Why do you take this number?

Re: TLE22

Posted by Zarhri 9 Jul 2017 15:04

big number N = X*Y*(p1*p2*p3*....*p18) = X*Y*(A)
A = at least 2^18 = 262144
So, X*Y = at most 10^18 / 2^18 = 3 814 697 266 000
So either X or Y is less than 10^7

Re: TLE22

Posted by Dmitry Shatunow 4 Nov 2019 22:16

Edited by author 05.11.2019 20:56

Edited by author 05.11.2019 20:57

Discussion of Problem 2102. Michael and Cryptography