Как найти ближайшее простое число?

Ответ 1

Вместо отсортированного списка простых чисел, учитывая относительно небольшой диапазон, заданный цели, имеет массив, проиндексированный всеми нечетными числами в диапазоне (вы знаете, что нет четных простых чисел, кроме специального случая 2) и содержащих ближайший простой, Поиск решения становится равным O (1) по времени.

Я думаю, что 100-е число составляет около 541. Массив из 270 [малых] ints - это все, что нужно.

Этот подход особенно важен, учитывая относительную высокую плотность простых чисел (в частности, относительно нечетных чисел), в диапазоне ниже 1000. (Так как это влияет на размер двоичного дерева)

Ответ 2

Если вам нужно искать только первые 100 простых чисел, просто создайте отсортированную таблицу этих простых чисел и выполните двоичный поиск. Это либо приведет вас к одному простому числу, либо месту между двумя, и вы проверите, какой из них ближе.

Изменить: учитывая распределение простых чисел в этом диапазоне, вы, вероятно, могли бы ускорить процесс (крошечный бит), используя поиск интерполяции - вместо того, чтобы всегда начинать с середины таблицы, используйте линейную интерполяцию, чтобы угадать более точную отправную точку. 100-е простое число должно быть где-то около 250 или около того (при угадывании - я не проверял), поэтому, если (например) вам нужен ближайший к 50, вы начнете примерно 1/5 пути в массив вместо половины. Вы можете в значительной степени относиться к простым числам, начиная с 1, поэтому просто разделите число, которое вы хотите, самым большим в вашем диапазоне, чтобы угадать исходную точку.

Ответ 3

Ответы до сих пор довольно сложны, учитывая поставленную задачу. Первые сотни простых чисел составляют менее 600. Я бы создал массив размером 600 и поместил в каждое значение ближайшего простого числа к этому числу. Затем, учитывая число для проверки, я бы оборачивал его вверх и вниз, используя функции floor и ceil, чтобы получить один или два ответа кандидата. Простое сравнение с расстояниями до этих чисел даст вам очень быстрый ответ.

Ответ 4

Самый простой способ - сохранить простые числа в отсортированном списке и изменить ваш алгоритм для выполнения двоичного поиска.

Стандартный алгоритм двоичного поиска возвращает null для промаха, но он должен быть прямым, чтобы изменить его для ваших целей.

Ответ 5

Самый быстрый алгоритм? Создайте таблицу поиска с p [100] = 541 элементами и верните результат для floor (x), со специальной логикой для x на [2,3]. Это будет O (1).

Ответ 6

Вы должны отсортировать свой номер в массиве, затем вы можете использовать двоичный поиск. Этот алгоритм - производительность O (log n) в худшем случае.

Ответ 7

В 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

Ответ 8

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

Ответ 9

Если вы хотите написать алгоритм, поиск в Wikipedia prime number привел меня к другой статье в Сито Эратосфена. Алгоритм выглядит немного просто, и я думаю, что рекурсивная функция будет хорошо импонирована. (Я мог ошибаться.)

Ответ 10

Если решение массива не подходит для вас (это лучший вариант для вашего сценария), вы можете попробовать код ниже. После случая "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;
}

Ответ 11

Таблица поиска whit размером 100 байт; (неподписанные символы) Круглый реальный номер и таблица поиска использования.

Ответ 12

Простейший ответ - Каждое простое число может быть представлено в виде (6 * x-1 и 6 * X +1) (кроме 2 и 3). пусть число будет N. Разделить его на 6. т = N/6; Теперь а = (т-1) * 6 б = (т + 1) * 6 и проверьте, какой из них ближе к N.

Ответ 13

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.