# 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!

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.

-
The basic calculation you're requestion was a sub-part of 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 Apr 9 '11 at 22:45
Can we use probabilistic primality tests? – Keith Randall Apr 10 '11 at 2:52
How 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 Apr 10 '11 at 3:41
@dmckee:No that problem is way more simple and very weak itself. – Quixotic Apr 10 '11 at 11:08
@Debanjan, may we assume the generalised Riemann hypothesis in stating time complexity? – Peter Taylor Apr 10 '11 at 15:40

## 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
``````
-

``````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..]

``````

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

-
 Sorry,that is not allowed,this is code challenge and I guess this should not work in the shorter version of the problem too. – Quixotic Apr 10 '11 at 14:44 As you said, importing code is a shame. Unless you judge others by another standard than your own – belisarius Dec 28 '12 at 0:09 @belisarius You err. This is not code golf so code size is not an option. The task you attempted to solve was code golf however. – FUZxxl Dec 28 '12 at 0:22 Using inbuilt primes is not a good choice as this is not codegolf and the whole point is to implement a fast approach This answer deserves a -1, clearly. I don't feel in a downvoting mood, though. – belisarius Dec 28 '12 at 1:18 @belisarius If you have the need for any sort of "revenge", just vote me down. There is no problem with that; neverthless, that is bad style. – FUZxxl Dec 28 '12 at 9:23

## 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())))
``````
-
 I suppose mathematica would be something similar but it's `NextPrime[n]` works strictly above `n` so 3 conditions.... – st0le Apr 16 '11 at 7:53

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
}
``````
-
 Using inbuilt primes is not a good choice as this is not codegolf and the whole point is to implement a fast approach,the decision of the best score is to be based on the complexity of the solution so this is not allowed,sorry. – Quixotic Apr 10 '11 at 14:46