Нахождение простого числа после заданного числа

Question

Как найти наименьшее простое число больше заданного числа? Например, учитывая 4, мне нужно 5; учитывая 7, мне нужно 11.

Я хотел бы знать некоторые идеи о лучших алгоритмах для этого. Один метод, о котором я подумал, - генерировать простые числа через сито Эратосфена и затем находить простое число после заданного числа.

Answer 1

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

Постулат Бертрана (фактически теорема) гласит, что если n> 3 является целым числом, то всегда существует хотя бы одно простое число p с n

1 всегда существует хотя бы одно простое число p, такое что n

Так что, если мне дают число, скажем, 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
    }
}

Answer 2

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

Единственным дополнением является теорема Бертранда из Ответ Раджендры .

И готовый код из 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's answer
        if(Miller(i,20)) // 18-20 iterations are enough for most of the applications.
            break;
    cout<<i<<endl;

    return 0;
}

Answer 3

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

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

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

Answer 4

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

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

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

Answer 5

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

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

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