serasesi's blog

POP1 on SPOJ
By serasesi, history, 8 years ago, In English

Hi, I was solving POP1 but can't get it to pass under the time limit.

Things I've tried.

  1. For detecting pop numbers, I simply brute force.
  2. For checking primes, I maintain an array of primes till 2e7 and after that apply Miller-Rabbin.

Here is my code.

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
8 years ago, hide # |
← Rev. 8  
Vote: I like it -14 Vote: I do not like it

First of all you can try to use linear prime sieve. Secondly, are you sure that your while does not work too long?

this while
→ Reply