# 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. Apr 9 '11 at 22:45
• Can we use probabilistic primality tests? 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. Apr 10 '11 at 3:41
• @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 :-) Apr 10 '11 at 11:27
• @Debanjan, may we assume the generalised Riemann hypothesis in stating time complexity? 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


## PARI GP

a(n)=x=[precprime(n),nextprime(n)];print(if(x[1]-n<n-x[2],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.... Apr 16 '11 at 7:53

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. Apr 10 '11 at 14:44
• As you said, importing code is a shame. Unless you judge others by another standard than your own 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. 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. 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. Dec 28 '12 at 9:23

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. Apr 10 '11 at 14:46

# Java

This takes <1 second until num starts being greater than 10^8. Not efficient enough, considering 2^64 is about 1.8*10^19. (Started 10^15 6 minutes ago, and is still running D:)

import java.util.*;

class ClosestPrime {

public static double closest(double num) {
double returnme = 0;
if (isPrime(num)){returnme = num;}
for (double i = 0; i < num / 2; i++) { //checks each side of num
if (isPrime(num - i)) {returnme = num - i;
break;}
if (isPrime(num + i)) {returnme = num + i;
break;}
}
return returnme;
}

private static boolean isPrime(double num) {
long sqrtnum = (long) Math.sqrt(num); //no need to check for factors above sqrt(num)
for (double i = 3; i < sqrtnum; i+=2) {primes.add(i);} //fill list with odd numbers

for (long i = 2; i <= sqrtnum; i++) {
if (num / i % 1 == 0) {return false;}
ListIterator<Double> iter = primes.listIterator();
while (iter.hasNext()) {if ((iter.next()) / i % 1 == 0){iter.remove();}} //sieving by Eratosthenes
}
return true;
}
}


This gives a surefire answer every time, since it doesn't use a probabilistic algorithm, but pays heavily for that in terms of efficiency - 10^18 would have over 5 million primes in the list, and even more before sieving. May improve this sometime with a better sieve algorithm. I don't expect this to beat any of the others :)

This is pretty fast, and non-deterministic up to a large limit. Also my first ever Haskell :). wc says 903b uncompiled.

Edit: If anyone wants to estimate the time complexity, be my guest...

import System.Environment
import Math.NumberTheory.Moduli -- arithmoi
import Data.List.Ordered -- data-ordlist

main :: IO ()
main = interact processInputStrings

processInputStrings :: String -> String
processInputStrings input = unlines $map show$ getClosestMembers $map read$ lines $input isPrime :: Integer -> Bool {- Implement the Miller–Rabin test with basis valid up to somewhere > 2^64 -} isPrime 2 = True isPrime 3 = True isPrime t = let factor :: (Integer, Integer) -> (Integer, Integer) factor (d,s) = if even d then factor (d div 2, s+1) else (d,s) (d,s) = factor (t-1, 0) in and$ map (\a ->
or [(powerMod a d t) == 1, or [(powerMod a (2^r * d) t) == t-1 | r <- [0..s-1]]]
) \$ filter (<t) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

getClosestMembers :: [Integer] -> [Integer]
getClosestMembers inputs = map (\i -> head [n | n <- concat [[i-d, i+d] | d <- [0..]], isPrime n]) inputs