Поиск простого числа после заданного числа

Ответ 1

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

В качестве альтернативы вы можете проверить все нечетные целые числа между (и включая) 3 и sqrt (N) на каждом номере с нечетным числом N, превышающим номер ввода, до тех пор, пока не найдете правильный номер. Конечно, вы можете остановить проверку, когда найдете ее составной.

Если вам нужен другой метод, я бы предложил использовать тест примитива Миллера-Рабина на всех нечетных числах над номером ввода (при условии, что входной сигнал > 1) до тех пор, пока не будет найдено штрих. Если вы выполните список, расположенный в нижней части страницы, чисел a, чтобы проверить заданные диапазоны, вы можете значительно сократить количество a, которое вам нужно проверить. Конечно, вы можете проверить, по крайней мере, несколько меньших простых чисел (например, 3,5,7,11), прежде чем проверять Миллера-Рабина.

Ответ 2

Источник: Википедия

постулат Бертрана (на самом деле теорема) гласит, что если n > 3 - целое число, то всегда существует хотя бы одно простое число p с n < p < 2n - 2. Более слабая, но более элегантная формулировка: для любого n > 1 всегда существует по крайней мере одно простое p такое, что n < p < 2n.

Итак, если мне присваивается число, скажем n, то я могу проверить диапазон (n, 2 * n) [открытый интервал, исключая n и 2 * n]

int GetNextPrime(int n)
{
    bool isPrime = false;
    for (int i = n; i < 2 * n; ++i)
    {
    // go with your regular prime checking routine
    // as soon as you find a prime, break this for loop
    }
}

Ответ 3

Я сделал это раньше.

Только добавление является теоремой Бертран из Ответ Раджендры.

И готовый код из topcoder.

#include<iostream>
using namespace std;

/* This function calculates (ab)%c */
int modulo(int a,int b,int c){
    long long x=1,y=a; // long long is taken to avoid overflow of intermediate results
    while(b > 0){
        if(b%2 == 1){
            x=(x*y)%c;
        }
        y = (y*y)%c; // squaring the base
        b /= 2;
    }
    return x%c;
}

/* this function calculates (a*b)%c taking into account that a*b might overflow */
long long mulmod(long long a,long long b,long long c){
    long long x = 0,y=a%c;
    while(b > 0){
        if(b%2 == 1){
            x = (x+y)%c;
        }
        y = (y*2)%c;
        b /= 2;
    }
    return x%c;
}

/* Miller-Rabin primality test, iteration signifies the accuracy of the test */
bool Miller(long long p,int iteration){
    if(p<2){
        return false;
    }
    if(p!=2 && p%2==0){
        return false;
    }
    long long s=p-1;
    while(s%2==0){
        s/=2;
    }
    for(int i=0;i<iteration;i++){
        long long a=rand()%(p-1)+1,temp=s;
        long long mod=modulo(a,temp,p);
        while(temp!=p-1 && mod!=1 && mod!=p-1){
            mod=mulmod(mod,mod,p);
            temp *= 2;
        }
        if(mod!=p-1 && temp%2==0){
            return false;
        }
    }
    return true;
}

int main(int argc, char* argv[])
{

    int input = 1000;
    int i = 0;

    if(input%2==0)
        i = input+1;
    else i = input;

    for(;i<2*input;i+=2) // from Rajendra answer
        if(Miller(i,20)) // 18-20 iterations are enough for most of the applications.
            break;
    cout<<i<<endl;

    return 0;
}

Ответ 4

У меня будет таблица с большим поиском, а затем найдите ее для данного номера и ответьте следующей в последовательности.

Хорошо работает, если существует известная (разумная) верхняя граница диапазона заданных чисел.

Ответ 5

Обычно я вижу два способа сделать это.

• подсчитывает из n и проверяет каждое число, чтобы оно было простым или не
• генерировать простые числа и проверять их. (возможно, сделайте это заранее, используйте существующую таблицу primenumber, поэтому вам не нужно каждый раз вычислять материал (ну, пока N находится в пределах диапазона вашей предварительно рассчитанной таблицы).

возможно, это тоже помогает (просто замените 2 вашим заданным числом и N бесконечным: D) найти все простые числа между 2 и N

Ответ 6

private static int nextPrime(int num) {
        num++;
        for (int i = 2; i <num; i++) {
            if(num%i == 0) {
                num++;
                i=2;
            } else{
                continue;
            }
        }
        return num;
    }