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

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

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

Answers so far are rather complicated, given the task in hand. The first hundred primes are all less then 600. I would create an array of size 600 and place in each the value of the nearest prime to that number. Then, given a number to test, I would round it both up and down using the floor and ceil functions to get one or two candidate answers. A simple comparison with the distances to these numbers will give you a very fast answer.

If you want to write an algorithm, A Wikipedia search for prime number led me to another article on the Sieve of Eratosthenes. The algorithm looks a bit simple and I'm thinking a recursive function would suit it well imo. (I could be wrong about that.)

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

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

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

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

If you only need to search in the first 100 primes or so, just create a sorted table of those primes, and do a binary search. This will either get you to one prime number, or a spot between two, and you check which of those is closer.

Edit: Given the distribution of primes in that range, you could probably speed things up (a tiny bit) by using an interpolation search -- instead of always starting at the middle of the table, use linear interpolation to guess at a more accurate starting point. The 100th prime number should be somewhere around 250 or so (at a guess -- I haven't checked), so if (for example) you wanted the one closest to 50, you'd start about 1/5th of the way into the array instead of halfway. You can pretty much treat the primes as starting at 1, so just divide the number you want by the largest in your range to get a guess at the starting point.