draak_krijger's blog

How can i reduce execution time ?
By draak_krijger, history, 10 years ago, In English

i solve it(The Most Complex Number) with .046s . how can solve it with .015s ? here my solution.
please , anyone give me some hints .

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You may hardcode all highly composite numbers and then answer every query in log time using binary search)

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

You can find the 1st 70 prime numbers and then for each 'n', loop through these numbers in the following way-

  1. Start from i=0, ans=1. ans=ans*prime[i] as long as ans<=n. i++.

  2. if ans*prime[i]>n, reset i=0 and repeat step 1 until its no longer possible. Maintain a hash of these primes you are using for frequency.

edit: we can pre calculate product of these primes in an array, and for each test case, we do a few binary searches. Why so many downvotes?

→ Reply