如何找到最近的素數？

Question

有沒有什麼好的算法來找到給定的real數字的最接近的素數？我只需要在前100個素數內進行搜索。

目前，我有一堆存儲在數組中的素數，我一次只檢查一個數字的差值（O（n）？）。

Answer 1

而不是排序的素數列表，如果目標的範圍相對較小，則會有一個由範圍內的所有奇數索引的數組（除了特殊情況2之外，沒有偶數個素數）幷包含最接近主要。尋找解決方案變成了O（1）的時間。

我認爲第100個素數大約是541.一個270 [小]整數的數組就是所需要的。

鑑於素數的相對高密度（特別是相對於奇數），此方法特別有效，在1000以下的範圍內。 （因爲這會影響二叉樹的大小）

Answer 2

最簡單的方法是將素數存儲在排序列表中並修改算法以執行二分搜索。

標準的二分查找算法會爲未命中返回null，但它應該是直接修改它爲您的目的。

Answer 3

您應該對數組進行排序，然後您可以使用binary search。該算法在最壞的情況下是O（log n）性能。

Answer 4

如果您只需要在前100個素數中進行搜索，只需創建這些素數的排序表，然後執行二分搜索。這將使您得到一個素數，或者兩個之間的一個點，然後檢查哪一個更接近。

編輯：鑑於素數在該範圍內的分佈，你也許可以加快速度（一點點），通過使用插值搜索 - 而不是總是開始在桌子中間，使用線性插值來猜測更準確的起點。第100個素數應該在250左右左右（猜測 - 我沒有檢查過），所以如果（例如）你想要最接近50的那個，你會開始大約1/5數組而不是中途。你幾乎可以把素數視爲從1開始，所以只需將你想要的數字除以範圍中最大的那個數就可以猜出起點。

Answer 5

最快的算法？使用p [100] = 541個元素創建一個查找表，並返回floor（x）的結果，對[2,3]上的x使用特殊的邏輯。那將是O（1）。

Answer 6

到目前爲止的答案相當複雜，給出了任務。第一百素數are all less then 600。我將創建一個大小爲600的數組，並將每個最接近該素數的素數值。然後，給定一個要測試的數字，我將使用floor和ceil函數向上和向下四捨五入來獲得一個或兩個候選答案。與這些數字的距離進行簡單比較將會給你一個非常快速的答案。

Answer 7

如果你想要寫一個算法，維基百科搜索prime number導致我在Sieve of Eratosthenes另一篇文章。該算法看起來有點簡單，我認爲遞歸函數會適合它。 （我可能是錯的。）

Answer 8

如果陣列解決方案對您來說不是一個有效的解決方案（它是您的場景中最好的解決方案），那麼可以嘗試下面的代碼。在「2或3」情況之後，它將檢查每個奇數的起始值，直到它找到一個素數。

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

查找的100個字節表絲毫大小; （無符號字符） 回合實數並使用查找表。

Answer 10

最簡單的答案 - 每個素數可以在形式（6 * X-1和6 * X 1）來表示（除2和3）。 讓數字爲N.用6分開。 t = N/6; 現在 A =（T-1）* 6 B =（T + 1）* 6 和檢查哪一個更接近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));} 

這是對於n> = 2。

Answer 12

在蟒蛇：

>>> 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; 
}