14

有没有什么好的算法可以找到最接近给定数字的素real数？我只需要在前 100 个素数左右进行搜索。

目前，我有一堆素数存储在一个数组中，我一次检查一个数字的差异（O（n）？）。

4

14 回答 14

18

考虑到目标范围相对较小，而不是排序的素数列表，而是有一个由该范围内的所有奇数索引的数组（您知道除了 2 的特殊情况之外没有偶数素数）并包含最接近的素数。找到解决方案在时间上变得 O(1)。

我认为第 100 个素数大约是 541。只需要 270 个 [小] 整数的数组。

考虑到素数的相对高密度（特别是相对于奇数），这种方法特别有效，在 1,000 以下的范围内。（因为这会影响二叉树的大小）

于 2009-10-15T21:21:14.277 回答
11

如果您只需要搜索前 100 个左右的素数，只需创建这些素数的排序表，然后进行二分搜索。这会让你得到一个素数，或者两个之间的一个点，然后你检查哪个更接近。

编辑：鉴于素数在该范围内的分布，您可能可以通过使用插值搜索来加快速度（一点点）——而不是总是从表格的中间开始，而是使用线性插值来猜测更准确的开始观点。第 100 个素数应该在 250 左右（猜测——我没有检查过），所以如果（例如）你想要最接近 50 的那个，你会从大约 1/5 开始数组而不是中途。您几乎可以将素数视为从 1 开始，因此只需将您想要的数字除以您范围内的最大值即可猜测起点。

于 2009-10-15T21:15:34.133 回答
8

鉴于手头的任务，到目前为止的答案相当复杂。前一百个素数都小于 600。我将创建一个大小为 600 的数组，并在每个数组中放置与该数字最接近的素数的值。floor然后，给定一个要测试的数字，我会使用and函数将其上下四舍五入，ceil以获得一两个候选答案。与这些数字的距离进行简单比较会给你一个非常快速的答案。

于 2009-10-15T21:25:02.427 回答
3

最快的算法？创建一个包含 p[100]=541 个元素的查找表并返回 floor(x) 的结果，其中 x 在 [2,3] 上的特殊逻辑。那将是O（1）。

于 2009-10-15T21:22:51.340 回答
3

最简单的方法是将素数存储在排序列表中并修改您的算法以进行二进制搜索。

标准的二分搜索算法将返回 null 以表示未命中，但为了您的目的应该直接对其进行修改。

于 2009-10-15T21:14:55.877 回答
2

您应该在数组中对您的号码进行排序，然后您可以使用二分搜索。该算法在最坏情况下的性能为 O(log n)。

于 2009-10-15T21:15:25.973 回答
1 
<?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;
}
于 2017-08-21T11:57:11.713 回答
1 
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。

于 2016-11-27T19:04:07.897 回答
1

在蟒蛇中：

>>> 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
于 2017-03-08T14:01:33.100 回答
0

Lookup table whit size of 100 bytes; (unsigned chars) Round real number and use lookup table.

于 2009-10-18T20:28:37.013 回答
0

如果数组解决方案对您来说不是一个有效的解决方案（它是您的方案的最佳解决方案），您可以尝试下面的代码。在“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;
}
于 2009-10-15T22:06:20.037 回答
0

如果你想写一个算法，在维基百科中搜索素数让我看到另一篇关于埃拉托色尼筛的文章。该算法看起来有点简单，我认为递归函数很适合 imo。（我可能错了。）

于 2009-10-15T21:30:15.940 回答
0

也许我们可以找到左右最近的素数，然后比较得到最接近的素数。（我假设下一个素数出现在接下来的 10 次中）

def leftnearestprimeno(n):
    n1 = n-1
    while(n1 >= 0):
        if isprime(n1):
            return n1
        else:
            n1 -= 1
    return -1

def rightnearestprimeno(n):
    n1 = n+1
    while(n1 < (n+10)):
        if isprime(n1):
            return n1
        else:
            n1 += 1

    return -1


n = int(input())
a = leftnearestprimeno(n)
b = rightnearestprimeno(n)
if (n - a) < (b - n):
    print("nearest: ", a)
elif (n - a) > (b - n):
    print("nearest: ", b)
else: 
    print("nearest: ", a)        #in case the difference is equal, choose min 
                                 #value
于 2020-08-24T20:47:21.107 回答
-2

最简单的答案 - 每个素数都可以用（6*x-1 和 6*X +1）的形式表示（2 和 3 除外）。设数为 N. 除以 6。 t=N/6; 现在 a=(t-1)*6 b=(t+1)*6 并检查哪个更接近 N。

于 2016-04-29T07:04:38.593 回答