Kode-Tantangan: Perdana Terdekat

8

Tantangan

Dalam tugas ini Anda akan diberi integer N Anda harus menampilkan bilangan prima terdekat ke bilangan bulat.

Jika bilangan prima itu sendiri menghasilkan bilangan.

Input N diberikan dalam satu baris, input diakhiri oleh EOF. Jumlah input tidak akan melebihi nilai 10000.

Tantangannya adalah untuk mengimplementasikan solusi tercepat sehingga dapat memproses maksimal 10.000 nilai secepat mungkin.

Memasukkan

 299246598
 211571591
 71266182
 645367642
 924278231

Keluaran

 299246587
 211571573
 71266183
 645367673
 924278233

Kendala

  • N kurang dari 2 ^ 64
  • Jaga jari-jari Anda jangan gunakan lebih dari 4096 byte dalam solusi Anda.
  • Anda dapat menggunakan bahasa apa pun pilihan Anda selama Anda tidak menggunakan bahasa inbuilt untuk bilangan prima.
  • Solusi tercepat, dengan kompleksitas waktu paling efisien menang!

TAMBAH:

Ini adalah versi yang lebih mudah dari masalah yang sama ini (dengan N <2 ^ 31) sehingga Anda dapat mencoba memeriksa pendekatan Anda dalam kasus yang lebih kecil sebelum membangunnya untuk masalah yang sebenarnya ini.

Pemurah
sumber
2
Perhitungan dasar yang Anda minta adalah sub-bagian dari codegolf.stackexchange.com/q/1977/78 , hanya beberapa hari yang lalu. Secara pribadi (yaitu tidak memakai topi moderator saya) saya merasa pengulangan seperti itu membosankan.
dmckee --- ex-moderator kitten
Bisakah kita menggunakan tes primality probabilistik?
Keith Randall
2
Bagaimana Anda berencana untuk menilai tercepat? Dengan kecepatan eksekusi pada perangkat keras tetap? Atau dengan menganalisis kompleksitas pengajuan? Apakah Anda akan menormalkan biaya operasi dalam berbagai bahasa? - Terakhir, tantangan ini tampaknya terlalu sederhana. Sebenarnya tidak ada ruang untuk berinovasi di sini.
MtnViewMark
1
@gnibbler: Menggunakan tabel pencarian dari semua nilai 2 ^ 64 akan memberi Anda solusi tercepat jika Anda dapat memeras seluruh hal (solusi) melalui jendela 4096 bytes :-)
Quixotic
2
@ Debanjan, dapatkah kita mengasumsikan hipotesis Riemann yang digeneralisasi dalam menyatakan kompleksitas waktu?
Peter Taylor

Jawaban:

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
sumber
Saya pikir perlu dicatat bahwa uji primitif Miller-Rabin tidak deterministik tanpa syarat. 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
sumber
Saya kira Mathematica akan menjadi sesuatu yang serupa tetapi ini NextPrime[n]berfungsi secara ketat di atas nsehingga 3 syarat ....
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

Seharusnya cukup cepat. Membutuhkan paket primes, tersedia dari peretasan.

FUZxxl
sumber
Maaf, itu tidak diizinkan, ini adalah tantangan kode dan saya kira ini seharusnya tidak berfungsi pada versi masalah yang lebih pendek.
Quixotic
Seperti yang Anda katakan, mengimpor kode adalah hal yang memalukan. Kecuali Anda menilai orang lain dengan standar lain dari standar Anda sendiri
Dr. belisarius
@belisarius Anda salah. Ini bukan kode golf sehingga ukuran kode bukan opsi. Namun, tugas yang Anda coba selesaikan adalah kode golf.
FUZxxl
1
Menggunakan bilangan prima bawaan bukanlah pilihan yang baik karena ini bukan codegolf dan intinya adalah menerapkan pendekatan cepat. Jawaban ini layak mendapatkan -1, jelas. Tapi aku tidak merasa sedih.
Dr. belisarius
@belisarius Jika Anda perlu "balas dendam", pilih saja saya. Tidak ada masalah dengan itu; Namun, itu adalah gaya yang buruk.
FUZxxl
0

Rubi

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
sumber
Menggunakan bilangan prima bawaan bukanlah pilihan yang baik karena ini bukan codegolf dan intinya adalah menerapkan pendekatan cepat, keputusan skor terbaik harus didasarkan pada kompleksitas solusi sehingga ini tidak diperbolehkan, maaf.
Quixotic
0

Jawa

Ini membutuhkan waktu <1 detik hingga num mulai lebih besar dari 10 ^ 8. Tidak cukup efisien, mengingat 2 ^ 64 adalah sekitar 1,8 * 10 ^ 19. (Dimulai 10 ^ 15 6 menit yang lalu, dan masih berjalan 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;
    }
}

Ini memberikan jawaban yang pasti setiap kali, karena tidak menggunakan algoritma probabilistik, tetapi membayar mahal untuk itu dalam hal efisiensi - 10 ^ 18 akan memiliki lebih dari 5 juta bilangan prima dalam daftar, dan bahkan lebih sebelum menyaring. Dapat meningkatkan ini kadang dengan algoritma ayakan yang lebih baik. Saya tidak berharap ini mengalahkan yang lain :)

Transformasi Fourier Rin
sumber
0

Haskell

Ini cukup cepat, dan non-deterministik hingga batas yang besar. Juga Haskell pertama saya :). wckata 903b tidak dikompilasi.

Sunting: Jika ada yang ingin memperkirakan kerumitan waktu, jadilah tamu saya ...

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
sumber