Discussion @ 2102. Michael and Cryptography @ Timus Online Judge

Kogut.Ivan TLE22 [6] // Problem 2102. Michael and Cryptography 20 Nov 2016 14:02

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

Felix_Mate Re: TLE22 [4] // Problem 2102. Michael and Cryptography 20 Nov 2016 21:22

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

esbybb Re: TLE22 [3] // Problem 2102. Michael and Cryptography 21 Nov 2016 08:57

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

esbybb Re: TLE22 // Problem 2102. Michael and Cryptography 21 Nov 2016 08:57

remaining typo

Kogut.Ivan Re: TLE22 [1] // Problem 2102. Michael and Cryptography 21 Nov 2016 21:40

Why do you take this number?

Zarhri Re: TLE22 // Problem 2102. Michael and Cryptography 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

Dmitry Shatunow Re: TLE22 // Problem 2102. Michael and Cryptography 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