Does anyone know how I can improve this Java code for better performance? It's giving timeout error for very big numbers.

Question

https://code.sololearn.com/cM0wyXcfugcO/?ref=app

Answer 1

10^18 is out of range. You would need to use BigInteger.

Answer 2

Barnabas Jonas Jonathas
I tried another version with long.
Highest test: 10^6
10^7 memory limit exceeded.

I think there is no way for really large numbers if you use the code playground. I don't know the memory limit and if it depends on the used language.

https://code.sololearn.com/cF1HdV44hch5/?ref=app

Answer 3

Input: 10 1000000
No timeout.

Answer 4

Yes your right. 10^19 would be out of range.

I am not sure if it would be better to make a list of primes using a sieve.

e.g. range 4 - 15
You just need the primes: 2,3,5,7,11,13

n inside the list? not semidivisible because its a prime. (5,7,11,13)
n = p*p not semidivisible (4 & 9)

Rest: 6, 8, 10, 12, 14, 15
Search inside the prime list for a number <= sqrt(6) -> get index
lps(6) = 2, index = 0
index + 1 = ups(6) //3, index = 1
And so on...

Answer 5

Barnabas Jonas Jonathas
Using a List is not good -> memory limit exceeded

I made a testcode with BigIntegers -> highest value ca. 2*10^4 (range: 8 - 20000)
Higher numbers: memory limit exeeded

https://code.sololearn.com/cGAZ4dIpRO9B/?ref=app

Answer 6

By very big, I mean as big as 10^18

Answer 7

I'm using long which goes up to 9,223,372,036,854,775,807...

Answer 8

Haven't had time to try this out yet, but surely will give it a try

Answer 9

Thanks for suggesting