8
Challenge
In this task you would be given an integer N you have to output the nearest prime to the integer.
If the number is prime itself output the number.
The input N is given in a single line,the inputs are terminated by EOF.The number of inputs would not exceed 10000 values.
The challenge is to implement the fastest solution so that it can process a maximum of 10000 values as fast as possible.
Input
299246598
211571591
71266182
645367642
924278231
Output
299246587
211571573
71266183
645367673
924278233
Constraints
- N is less than 2^64
- Take care of your fingers do not use more than 4096 bytes in your solution.
- You can use any language of your choice as long as you are not using it's any inbuilt things for the primes.
- Fastest solution,with the most efficient time complexity wins!
ADDED:
This is a easier version of the this same problem (with N < 2^31) so that you may try checking your approach in smaller cases before building it up for this actual problem.
Would you provide some more test data please? – alexander-brett – 2015-04-21T08:54:19.290
2
The basic calculation you're requestion was a sub-part of http://codegolf.stackexchange.com/q/1977/78, just a couple of days ago. Personally (i.e. not wearing my moderator hat) I find such repetition boring.
– dmckee --- ex-moderator kitten – 2011-04-09T22:45:09.943Can we use probabilistic primality tests? – Keith Randall – 2011-04-10T02:52:58.117
2How do you plan on judging fastest? By speed of execution on fixed hardware? Or by analyzing the complexity of the submissions? Will you somehow normalize the cost of operations in different languages? -- Lastly, this challenge seems way too simple. There really isn't any room to innovate here. – MtnViewMark – 2011-04-10T03:41:10.223
@dmckee:No that problem is way more simple and very weak itself. – Quixotic – 2011-04-10T11:08:21.010
Can I use a 2^64 lookup table? – gnibbler – 2011-04-10T11:09:09.460
@Keith Randall:My solution is developed on Miller-Rabin + an optimized sieve for small numbers but you may use fast deterministic tests too :-) – Quixotic – 2011-04-10T11:15:33.207
@MtnViewMark:I have mentioned in the constraints that the
Fastest solution,with the most efficient time complexity wins!
and I think it is not that simple,please take a look on the restrictions (carefully) and if you still find itway more simple
and there isn't any room for innovation,then I am sorry,probably this challenge is not for you :-) – Quixotic – 2011-04-10T11:19:20.4131@gnibbler: Using a lookup table of all 2^64 values will give you the fastest solution iff you can squeeze the entire thing (solution) through the 4096 bytes window :-) – Quixotic – 2011-04-10T11:27:23.903
2@Debanjan, may we assume the generalised Riemann hypothesis in stating time complexity? – Peter Taylor – 2011-04-10T15:40:13.863
@Peter Taylor: Okay :-) – Quixotic – 2011-04-10T17:40:14.960