Last case TLE in Primality Testing

#1

please look upto my code and tell me my the last case shows TLE

Here’s the github gist

#2

use little fermate theorem…

1 Like
#3

you cannot check if a number is prime or not with this method if number is as large as 2^64

#4

ok thanks I will try that way

#5

i guess the last test case has been designed so that it fails the probabilistic algo …then what do i do??

#6

no it wont fail… just take care of overflow while multiplying large number…

#7

yes I took care of it using modulo exponentiation but it still fails

#8

a = 1e14 + 1

b = 1e4 + 2

c = 1e15

how will you evaluate (a*b)%c ?

#9

But c was supposed to be 10e9+7,
In the case you mentioned it will overflow

#10

in little fermate c is not equal to 1e9+7 c is the number and number can vary upto 1e18. thats why i told you to take care of overflow while multiplying large number.

1 Like
#11

see my code how to handle such situation

#12
#13

got my mistake in this part !!