8
\$\begingroup\$

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.

\$\endgroup\$
11
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ Apr 9 '11 at 22:45
  • \$\begingroup\$ Can we use probabilistic primality tests? \$\endgroup\$ Apr 10 '11 at 2:52
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ Apr 10 '11 at 3:41
  • 1
    \$\begingroup\$ @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 :-) \$\endgroup\$
    – Quixotic
    Apr 10 '11 at 11:27
  • 2
    \$\begingroup\$ @Debanjan, may we assume the generalised Riemann hypothesis in stating time complexity? \$\endgroup\$ Apr 10 '11 at 15:40
6
\$\begingroup\$

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
\$\endgroup\$
1
2
\$\begingroup\$

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

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.

\$\endgroup\$
5
  • \$\begingroup\$ Sorry,that is not allowed,this is code challenge and I guess this should not work in the shorter version of the problem too. \$\endgroup\$
    – Quixotic
    Apr 10 '11 at 14:44
  • \$\begingroup\$ As you said, importing code is a shame. Unless you judge others by another standard than your own \$\endgroup\$ Dec 28 '12 at 0:09
  • \$\begingroup\$ @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. \$\endgroup\$
    – FUZxxl
    Dec 28 '12 at 0:22
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Dec 28 '12 at 1:18
  • \$\begingroup\$ @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. \$\endgroup\$
    – FUZxxl
    Dec 28 '12 at 9:23
0
\$\begingroup\$

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
}
\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$
    – Quixotic
    Apr 10 '11 at 14:46
0
\$\begingroup\$

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)
        List<Double> primes = new LinkedList<Double>();
        primes.add((double) 2);
        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 :)

\$\endgroup\$
0
\$\begingroup\$

Haskell

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.