Code-Challenge:The Nearest Prime

Question

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.

Answer 1

Python

import sys,random

# Miller-Rabin primality test, error rate 2^-200.                                                                                                                           
def prime(N):
  if N<3:return N==2
  s=0
  d=N-1
  while (d&1)==0:s+=1;d>>=1
  for i in xrange(100):
    a=random.randrange(1,N)
    if pow(a,d,N)!=1 and all(pow(a,d<<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

Answer 2

Haskell

import Data.Numbers.Primes

-- Assuming, we are on x64
nearestPrime :: Int -> Int
nearestPrime n | n - s < l - n = s
               | otherwise     = l where
  l = head $ dropWhile (not . isPrime) [n..]
  s = head $ dropWhile (not . isPrime) [n,n-1..]

main = readLine >>= print . nearestPrime . read

Should be quite fast. Requires the package primes, available from hackage.

Answer 3

PARI GP

a(n)=x=[precprime(n),nextprime(n)];print(if(2*n-x[1]-x[2]<0,x[1],x[2]))
while(1,print(a(input())))

Answer 4

Ruby

require 'prime'
gets(p).split.each{|n|
    a=b=n.to_i
    a,b = a-1,b+1 while !a.prime?  and !b.prime?
    p a.prime? ? a : b
}