Comment puis-je trouver le nombre premier le plus proche?

Est-il agréable algorithme pour trouver le plus proche de nombre premier donné real nombre? J'ai seulement besoin de chercher dans les 100 premiers nombres premiers.

À l'heure actuelle, j'ai un tas de nombres premiers stockées dans un tableau et je suis en cochant la différence d'un nombre en un temps O(n)?).

source d'informationauteur Marty

algorithm primes

17

Plutôt que d'une liste ordonnée de nombres premiers, compte tenu de la taille relativement petite de la gamme ciblée, ont un tableau indexé par tous les nombres impairs dans la gamme (vous savez, il n'y a pas encore les nombres premiers sauf le cas particulier de 2) et contenant le plus proche du premier. Trouver la solution devient O(1) sur le plan du temps.

Je pense que le 100e premier est d'environ 541. un tableau de 270 [petit] ints est tout ce qui est nécessaire.

Cette approche est particulièrement valable, compte tenu de la relative forte densité des nombres premiers (en particulier par rapport aux nombres impairs), dans la gamme en dessous de 1 000. (Ce qui affecte la taille d'un arbre binaire)
11

Si vous avez seulement besoin de chercher dans les 100 premiers nombres premiers, il suffit de créer un tableau trié de ces nombres premiers, et de faire une recherche binaire. Ce sera soit un nombre premier, ou un endroit entre les deux, et vous vérifiez celles qui est la plus proche.

Edit: compte tenu de la répartition des nombres premiers dans cette gamme, vous pourriez probablement accélérer les choses (un petit peu) à l'aide d'une interpolation de recherche -- au lieu de toujours en commençant au milieu de la table, utiliser une interpolation linéaire à deviner le plus de précision le point de départ. Le 100e nombre premier devrait être d'environ 250 (à un pense-je n'ai pas vérifié), donc (par exemple) si vous voulais le plus proche de 50, vous commenceriez à environ 1/5ème de la manière dans le tableau au lieu de la moitié. Vous pouvez très bien traiter les primes comme commençant à 1, il suffit donc de diviser le nombre que vous voulez le plus à votre portée pour obtenir une deviner le point de départ.
8

De réponses sont plutôt compliqué, compte tenu de la tâche à accomplir. Les cent premiers nombres premiers sont tous à moins de 600. Je voudrais créer un tableau de taille 600 et place dans chacun, la valeur de la plus proche du premier que du nombre. Ensuite, étant donné un nombre à tester, je voudrais arrondir vers le haut et vers le bas à l'aide de la floor et ceil fonctions pour obtenir un ou deux réponses données par le candidat. Une simple comparaison avec les distances à ces numéros, vous donnera une très rapide réponse.
3

L'approche la plus simple serait de stocker les nombres premiers dans une liste triée et modifier votre algorithme pour effectuer une recherche binaire.

La norme binaire de l'algorithme de recherche serait de retourner la valeur null pour une miss, mais il devrait être simple de le modifier pour vos besoins.
3

L'algorithme le plus rapide? Créer une table avec p[100]=541 éléments et de retourner le résultat de plancher(x), avec une logique spéciale pour x sur [2,3]. Que serait O(1).
2

Vous devez trier votre numéro dans tableau, alors vous pouvez utiliser recherche binaire. Cet algorithme est O(log n) de la performance dans le pire des cas.

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

c'est pour le n>=2.

En 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

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

0

Si vous voulez écrire un algorithme, Un Wikipedia de recherche pour le premier numéro de m'a conduit à un autre article sur le Crible d'Eratosthène. L'algorithme semble un peu simple et je pense à une fonction récursive qui irait bien de l'omi. (Je peux me tromper à ce sujet.)

Si la solution de matrice n'est pas une solution valable pour vous (c'est la meilleure solution pour votre scénario, vous pouvez essayer le code ci-dessous. Après le "2 ou 3" le cas, il vérifie chaque nombre impair à l'écart de la valeur de départ jusqu'à ce qu'il trouve un nombre premier.

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

0

Table de recherche de pentecôte taille de 100 octets; (unsigned caractères)
Tour de nombre réel et de l'utilisation de la table de choix.
0

Réponse la plus simple-
Chaque nombre premier peut être représenté sous la forme (6*x-1 et 6*X +1) (à l'exception des 2 et 3).
laissez numéro N. le diviser par 6.
t=N/6;
maintenant
a=(t-1)*6
b=(t+1)*6
et voir laquelle est la plus proche de N.

Vous devez vous connecter pour publier un commentaire.