Jak znaleźć najbliższą liczbę pierwszą?

Question

Czy istnieje dobry algorytm znajdowania najbliższej liczby pierwszej dla danego numeru real? Muszę przeszukać tylko w ciągu pierwszych 100 liczb pierwszych.

Obecnie mam kilka liczb pierwszych przechowywanych w tablicy i sprawdzam różnicę jedną liczbę na raz (O (n)?).

Answer 1

Zamiast uporządkowanej listy liczb pierwszych, biorąc pod uwagę stosunkowo mały zasięg, mają one tablicę indeksowaną przez wszystkie liczby nieparzyste w zakresie (wiesz, że nie ma żadnych liczb pierwszych, z wyjątkiem przypadku specjalnego 2) i zawierają najbliższy główny. Znalezienie rozwiązania staje się O (1) w czasie.

Myślę, że 100. premiera to około 541. tablica 270 [małych] int jest wszystkim, co jest potrzebne.

Podejście to jest szczególnie uzasadnione, biorąc pod uwagę względną wysoką gęstość liczb pierwszych (w szczególności w odniesieniu do liczb nieparzystych) w zakresie poniżej 1000. (Ponieważ ma to wpływ na rozmiar drzewa binarnego)

Answer 2

Najprostszym podejściem byłoby przechowywanie liczb pierwszych na posortowanej liście i zmodyfikowanie algorytmu w celu wyszukiwania binarnego.

Standardowy algorytm wyszukiwania binarnego zwróci wartość zerową dla pominięcia, ale powinna być prosta do modyfikacji w celu.

Answer 3

Powinieneś posortować swój numer w tablicy, a następnie użyć binary search. Ten algorytm jest w najgorszym przypadku wynikiem O (log n).

Answer 4

Jeśli potrzebujesz przeszukać tylko pierwszych 100 liczb pierwszych, po prostu utwórz posortowaną tabelę tych liczb pierwszych i przeprowadź wyszukiwanie binarne. Spowoduje to przejście do jednej liczby pierwszej lub do miejsca między dwoma, a także sprawdzenie, która z nich jest bliżej.

Edycja: Biorąc pod uwagę rozkład liczb pierwszych w tym zakresie, prawdopodobnie można przyspieszyć działanie (odrobinę) za pomocą wyszukiwania interpolacyjnego - zamiast zawsze zaczynać od środka tabeli, użyj interpolacji liniowej, aby odgadnąć dokładniejszy punkt wyjścia. 100. liczba pierwsza powinna wynosić około 250 (według przypuszczeń - nie sprawdziłem), więc jeśli (na przykład) chciałbyś mieć najbliższą 50, zaczynasz około 1/5 swojej tablica zamiast w połowie. Możesz w zasadzie traktować liczby pierwsze jako od 1, więc po prostu podziel numer, który chcesz, przez największy w swoim zakresie, aby uzyskać domysły w punkcie wyjścia.

Answer 5

Najszybszy algorytm? Utwórz tabelę odnośników z p [100] = 541 elementami i zwróć wynik dla piętra (x), ze specjalną logiką dla x na [2,3]. To byłby O (1).

Answer 6

Odpowiedzi do tej pory są dość skomplikowane, biorąc pod uwagę zadanie w ręku. Pierwsza setka liczb pierwszych are all less then 600. Utworzyłem tablicę o wielkości 600 i umieściłem każdą wartość najbliższej liczby pierwszej na tej liczbie. Następnie, biorąc pod uwagę liczbę do przetestowania, zaokrąglałem ją zarówno w górę, jak iw dół, używając funkcji floor i ceil, aby uzyskać jedną lub dwie odpowiedzi kandydujące. Proste porównanie z odległościami do tych liczb da bardzo szybką odpowiedź.

Answer 7

Jeśli chcesz napisać algorytm, wyszukiwanie w Wikipedii pod adresem prime number doprowadziło mnie do innego artykułu na temat Sieve of Eratosthenes. Algorytm wygląda trochę prosto i myślę, że funkcja rekursywna dobrze by mu pasowała. (Mogłem się mylić.)

Answer 8

Jeśli rozwiązanie macierzowe nie jest dla ciebie właściwym rozwiązaniem (jest najlepsze dla twojego scenariusza), możesz wypróbować poniższy kod. Po przypadku "2 lub 3", sprawdza każdą liczbę nieparzystą od wartości początkowej, aż znajdzie liczbę pierwszą.

static int NearestPrime(double original) 
{ 
    int above = (int)Math.Ceiling(original); 
    int below = (int)Math.Floor(original); 

    if (above <= 2) 
    { 
     return 2; 
    } 

    if (below == 2) 
    { 
     return (original - 2 < 0.5) ? 2 : 3; 
    } 

    if (below % 2 == 0) below -= 1; 
    if (above % 2 == 0) above += 1; 

    double diffBelow = double.MaxValue, diffAbove = double.MaxValue; 

    for (; ; above += 2, below -= 2) 
    { 
     if (IsPrime(below)) 
     { 
      diffBelow = original - below; 
     } 

     if (IsPrime(above)) 
     { 
      diffAbove = above - original; 
     } 

     if (diffAbove != double.MaxValue || diffBelow != double.MaxValue) 
     { 
      break; 
     } 
    } 

    //edit to your liking for midpoint cases (4.0, 6.0, 9.0, etc) 
    return (int) (diffAbove < diffBelow ? above : below); 
} 

static bool IsPrime(int p) //intentionally incomplete due to checks in NearestPrime 
{ 
    for (int i = 3; i < Math.Sqrt(p); i += 2) 
    { 
     if (p % i == 0) 
      return false; 
    } 

    return true; 
} 

Answer 9

wyszukiwania wielkość tabeli rozróżnialnych 100 bajtów; (unsigned chars) Okrągła liczba rzeczywista i użyj tabeli odnośników.

Answer 10

Najprostsza odpowiedź- Każda liczba pierwsza może być reprezentowana w formularzu (6 * x-1 i 6 * X +1) (oprócz 2 i 3). Niech numer jest N.divide it 6. t = N/6; teraz A = (T-1) * 6 b = (T + 1) * 6 i sprawdzić, który z nich jest bliżej N.

Answer 11

public static boolean p(int n){ 

    for(int i=3;i*i<=n;i+=2) { 
     if(n%i==0) 
      return false; 
    } 
    return n%2==0? false: true; } 

public static void main(String args[]){ 
    String n="0"; 
    int x = Integer.parseInt(n); 
    int z=x; 
    int a=0; 
    int i=1; 
    while(!p(x)){ 

     a = i*(int)Math.pow(-1, i); 
     i++; 
     x+=a; 
    } 

    System.out.println((int) Math.abs(x-z));} 

to jest dla n> = 2.

Answer 12

W python:

>>> def nearest_prime(n): 
    incr = -1 
    multiplier = -1 
    count = 1 
    while True: 
     if prime(n): 
      return n 
     else: 
      n = n + incr 
      multiplier = multiplier * -1 
      count = count + 1 
      incr = multiplier * count 

>>> nearest_prime(3) 
3 
>>> nearest_prime(4) 
3 
>>> nearest_prime(5) 
5 
>>> nearest_prime(6) 
5 
>>> nearest_prime(7) 
7 
>>> nearest_prime(8) 
7 
>>> nearest_prime(9) 
7 
>>> nearest_prime(10) 
11 

Answer 13

<?php 
$N1Diff = null; 
$N2Diff = null; 

$n1 = null; 
$n2 = null; 

$number = 16; 

function isPrime($x) { 

    for ($i = 2; $i < $x; $i++) { 
     if ($x % $i == 0) { 
      return false; 
     } 
    } 

    return true; 
} 


for ($j = $number; ; $j--) { 

    if(isPrime($j)){ 
     $N1Diff = abs($number - $j); 
     $n1 = $j; 
     break; 
    } 
} 


for ($j = $number; ; $j++) { 

    if(isPrime($j)){ 
     $N2Diff = abs($number - $j); 
     $n2 = $j; 
     break; 
    } 

} 

if($N1Diff < $N2Diff) { 

    echo $n1; 

} else if ($N1Diff2 < $N1Diff){ 
    echo $n2; 
}