Saturday, July 16, 2016

SPOJ: Prime Number Generator

Here is my first attempt at solving for SPOJ PRIME1 - Prime Generator. This one times out though I have a few ideas I thought I'd pen down for future implementations:

  • Prime generator: survey literature for given a range(x, y): best way to generate primes. In terms of primality tests -- there is no dearth of these. Miller-Rabin is quite well-studied.
  • Seeds: Find the best way to store all the seeds needed -- do I need to create a lookup for primes? or some other seeds. The space limits provided are of 1.5 Gig -- which can easily hold a hard-coded  list, though I'm not certain one would hit paging bottlenecks.
  • Create range lookups for already looked up primes: So, we get ranges (xi, yi) -- so long as  we can find the super-ranges from these such that they reduce these sets to cover all ranges asked for -- we can generate fewer lists and hold. This super-ranges should reduce the waste of re-producing the same lists
  • I'm not entirely certain if we will hit memory issues in which case might have to re-arch to spit out as we go.

    EDIT: None of the above was neccessary, just used the code from Rosetta Code to make it accept the timelines. Need to start using some profiling tools in the future to help with optimizing on mem and time.

EDIT: The on that passed:

No comments:

Post a Comment