Code-Challenge:The Nearest Prime 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 &lt; 2^31) so that you may try checking your approach in smaller cases before building it up for this actual problem.
Python

import sys,random

# Miller-Rabin primality test, error rate 2^-200.                                                                                                                           
def prime(N):
  if N&lt;3:return N==2
  s=0
  d=N-1
  while (d&amp;1)==0:s+=1;d&gt;&gt;=1
  for i in xrange(100):
    a=random.randrange(1,N)
    if pow(a,d,N)!=1 and all(pow(a,d&lt;&lt;r,N)!=N-1 for r in xrange(s)):return 0
  return 1

for N in map(int,sys.stdin):
  d=0
  while 1:
    if prime(N+d):print N+d;break
    if prime(N-d):print N-d;break
    d+=1