Code-Challenge: Der nächste Prime

8

Herausforderung

In dieser Aufgabe erhalten Sie eine Ganzzahl N, für die Sie die der Ganzzahl nächstgelegene Primzahl ausgeben müssen.

Wenn die Zahl selbst eine Primzahl ist, geben Sie die Zahl aus.

Der Eingang N wird in einer einzelnen Zeile angegeben, die Eingänge werden durch EOF abgeschlossen. Die Anzahl der Eingänge würde 10000 Werte nicht überschreiten.

Die Herausforderung besteht darin, die schnellste Lösung zu implementieren, damit maximal 10000 Werte so schnell wie möglich verarbeitet werden können.

Eingang

 299246598
 211571591
 71266182
 645367642
 924278231

Ausgabe

 299246587
 211571573
 71266183
 645367673
 924278233

Einschränkungen

  • N ist kleiner als 2 ^ 64
  • Achten Sie auf Ihre Finger. Verwenden Sie nicht mehr als 4096 Byte in Ihrer Lösung.
  • Sie können jede Sprache Ihrer Wahl verwenden, solange Sie keine eingebauten Dinge für die Primzahlen verwenden.
  • Die schnellste Lösung mit der effizientesten Zeitkomplexität gewinnt!

HINZUGEFÜGT:

Dies ist eine einfachere Version desselben Problems (mit N <2 ^ 31), sodass Sie versuchen können, Ihren Ansatz in kleineren Fällen zu überprüfen, bevor Sie ihn für dieses eigentliche Problem erstellen.

Quixotic
quelle
2
Die Grundberechnung, die Sie anfordern, war vor ein paar Tagen ein Teil von codegolf.stackexchange.com/q/1977/78 . Persönlich (dh ohne meinen Moderatorhut) finde ich solche Wiederholungen langweilig.
dmckee --- Ex-Moderator Kätzchen
Können wir probabilistische Primalitätstests verwenden?
Keith Randall
2
Wie wollen Sie am schnellsten urteilen? Nach Ausführungsgeschwindigkeit auf fester Hardware? Oder indem Sie die Komplexität der Einreichungen analysieren? Werden Sie die Betriebskosten in verschiedenen Sprachen irgendwie normalisieren? - Schließlich scheint diese Herausforderung viel zu einfach. Hier gibt es wirklich keinen Raum für Innovationen.
MtnViewMark
1
@gnibbler: Wenn Sie eine Nachschlagetabelle mit allen 2 ^ 64-Werten verwenden, erhalten Sie die schnellste Lösung, wenn Sie die gesamte Sache (Lösung) durch das 4096-Byte-Fenster drücken können :-)
Quixotic
2
@Debanjan, können wir die verallgemeinerte Riemann-Hypothese bei der Angabe der Zeitkomplexität annehmen?
Peter Taylor

Antworten:

6

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
Keith Randall
quelle
Ich denke, es sollte angemerkt werden, dass der Miller-Rabin-Primalitätstest nicht unbedingt deterministisch ist. en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
mbomb007
2

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())))
st0le
quelle
Ich nehme an, Mathematica wäre etwas Ähnliches, aber es NextPrime[n]funktioniert streng über n3 Bedingungen ....
st0le
0

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

Sollte ziemlich schnell sein. Benötigt das Paket primes, verfügbar von Hackage.

FUZxxl
quelle
Entschuldigung, das ist nicht erlaubt, dies ist eine Code-Herausforderung und ich denke, dies sollte auch in der kürzeren Version des Problems nicht funktionieren.
Quixotic
Wie Sie sagten, ist das Importieren von Code eine Schande. Es sei denn, Sie beurteilen andere nach einem anderen Maßstab als Ihrem eigenen
Dr. belisarius
@ Belisarius Sie irren. Dies ist kein Code Golf, daher ist die Codegröße keine Option. Die Aufgabe, die Sie zu lösen versuchten, war jedoch Code Golf.
FUZxxl
1
Die Verwendung eingebauter Primzahlen ist keine gute Wahl, da dies kein Codegolf ist und der springende Punkt darin besteht, einen schnellen Ansatz zu implementieren. Diese Antwort verdient eindeutig eine -1. Ich fühle mich jedoch nicht schlecht gelaunt.
Dr. Belisarius
@belisarius Wenn du irgendeine Art von "Rache" brauchst, stimme mich einfach ab. Damit ist kein Problem verbunden. Trotzdem ist das ein schlechter Stil.
FUZxxl
0

Rubin

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
}
st0le
quelle
Die Verwendung eingebauter Primzahlen ist keine gute Wahl, da dies kein Codegolf ist und der springende Punkt darin besteht, einen schnellen Ansatz zu implementieren. Die Entscheidung über die beste Punktzahl muss auf der Komplexität der Lösung basieren, sodass dies leider nicht zulässig ist.
Quixotic
0

Java

Dies dauert <1 Sekunde, bis num größer als 10 ^ 8 wird. Nicht effizient genug, wenn man bedenkt, dass 2 ^ 64 ungefähr 1,8 * 10 ^ 19 ist. (Begonnen vor 10 ^ 15 6 Minuten und läuft immer noch 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;
    }
}

Dies gibt jedes Mal eine todsichere Antwort, da kein probabilistischer Algorithmus verwendet wird, dies jedoch in Bezug auf die Effizienz stark bezahlt wird - 10 ^ 18 hätte mehr als 5 Millionen Primzahlen in der Liste und noch mehr vor dem Sieben. Kann dies irgendwann mit einem besseren Siebalgorithmus verbessern. Ich erwarte nicht, dass dies einen der anderen schlägt :)

Rins Fourier-Transformation
quelle
0

Haskell

Dies ist ziemlich schnell und bis zu einer großen Grenze nicht deterministisch. Auch mein allererster Haskell :). wcsagt 903b unkompiliert.

Bearbeiten: Wenn jemand die zeitliche Komplexität abschätzen möchte, sei mein Gast ...

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
alexander-brett
quelle