14

与えられた数に最も近い素数を見つけるための素晴らしいアルゴリズムはありますrealか？最初の100素数程度で検索するだけです。

現在、私はたくさんの素数を配列に格納していて、一度に1つの数の差をチェックしています（O（n）？）。

4

14 に答える 14

18

対象となる範囲が比較的小さい場合、素数の並べ替えられたリストではなく、範囲内のすべての奇数でインデックス付けされた配列があり（2の特殊なケースを除いて偶数の素数はないことがわかります）、最も近い素数が含まれます。解を見つけることは時間的にO（1）になります。

100番目の素数は約541だと思います。必要なのは270[小さい]intの配列だけです。

このアプローチは、1,000未満の範囲で、（特に奇数に対して）素数の密度が比較的高い場合に特に有効です。（これは二分木のサイズに影響するため）

于 2009-10-15T21:21:14.277 に答える
11

最初の100個程度の素数だけを検索する必要がある場合は、それらの素数のソートされたテーブルを作成し、バイナリ検索を実行します。これにより、1つの素数、または2つの間のスポットのいずれかに到達し、どちらが近いかを確認します。

編集：その範囲の素数の分布を考えると、補間検索を使用することでおそらくスピードアップ（ほんの少し）することができます-常にテーブルの中央から開始するのではなく、線形補間を使用してより正確な開始を推測します点。100番目の素数は約250程度である必要があります（推測では-私はチェックしていません）。したがって、（たとえば）50に最も近い素数が必要な場合は、約1/5から始めます。途中ではなく配列。素数は1から始まるものとして扱うことができるので、必要な数を範囲内の最大数で割って、開始点を推測します。

于 2009-10-15T21:15:34.133 に答える
8

手元のタスクを考えると、これまでの回答はかなり複雑です。最初の100個の素数はすべて600未満です。サイズ600の配列を作成し、それぞれにその数に最も近い素数の値を配置します。floor次に、テストする数値を指定して、 and関数を使用して切り上げと切り下げを行い、 ceil1つまたは2つの候補の回答を取得します。これらの数値までの距離を簡単に比較すると、非常に迅速な回答が得られます。

于 2009-10-15T21:25:02.427 に答える
3

最も簡単なアプローチは、素数をソートされたリストに格納し、アルゴリズムを変更して二分探索を行うことです。

標準の二分探索アルゴリズムは、ミスに対してnullを返しますが、目的に合わせて変更するのは簡単です。

于 2009-10-15T21:14:55.877 に答える
3

最速のアルゴリズム？p [100] = 541要素でルックアップテーブルを作成し、[2,3]のxに特別なロジックを使用して、floor（x）の結果を返します。それはO（1）になります。

于 2009-10-15T21:22:51.340 に答える
2

あなたは配列であなたの数をソートするべきです、そしてあなたは二分探索を使うことができます。このアルゴリズムは、最悪の場合のO（log n）パフォーマンスです。

于 2009-10-15T21:15:25.973 に答える
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

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

アルゴリズムを書きたい場合は、ウィキペディアで素数を検索すると、エラトステネスのふるいに関する別の記事が表示されます。アルゴリズムは少し単純に見えますが、再帰関数がそれに適していると思います。（私はそれについて間違っている可能性があります。）

于 2009-10-15T21:30:15.940 に答える
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

100バイトのルックアップテーブルの聖霊降臨祭のサイズ。（unsigned chars）実数を丸め、ルックアップテーブルを使用します。

于 2009-10-18T20:28:37.013 に答える
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 に答える