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

Question

Питер хочет сгенерировать несколько простых чисел для своей криптосистемы. Помоги ему! Ваша задача - сгенерировать все простые числа между двумя заданными числами!

Входные данные Входные данные начинаются с числа t тестовых примеров в единственной строке (t <= 10). В каждой из следующих t строк есть два числа m и n (1 <= m <= n <= 1000000000, nm <= 100000), разделенные пробелом. </p>

Выходные данные Для каждого теста выведите все штрихи числа p такие, что m <= p <= n, по одному числу в строке, тестовые примеры разделены пустой строкой. </p>

Пример ввода:

2
1 10
3 5

Вывод:

2
3
5
7

3
5

Предупреждение: большие данные ввода / вывода, будьте осторожны с некоторыми языками (хотя большинство из них должно быть в порядке, если алгоритм хорошо спроектирован)

Я поискал в Google, чтобы найти решение для оптимизации вышеупомянутой проблемы и вот код.

#include <iostream>
#include <cmath>
#include <vector>
#include <set>
using namespace std;

int main() {
    vector<int> primes;
    primes.push_back(2);

    for (int i = 3; i <= 32000; i+=2) {
        bool isprime = true;
        int cap = sqrt(i) + 1;

        vector<int>::iterator p;
        for (p = primes.begin(); p != primes.end(); p++) {
            if (*p >= cap) break;
            if (i % *p == 0) {
                isprime = false;
                break;
            }
        }
        if (isprime) primes.push_back(i);
    }

    int T,N,M;

    cin >> T;

    for (int t = 0; t < T; t++) {
        if (t) cout << endl;

        cin >> M >> N;
        if (M < 2) M = 2;

        int cap = sqrt(N) + 1;

        set<int> notprime;
        notprime.clear();

        vector<int>::iterator p;
        for (p = primes.begin(); p != primes.end(); p++) {

            if (*p >= cap) break;
            int start;

            if (*p >= M) start = (*p)*2;
            else start = M + ((*p - M % *p) % *p); //not able to understand this logic.

            for (int j = start; j <= N; j += *p) {
                notprime.insert(j);
            }
        }

        for (int i = M; i <= N; i++) {
            if (notprime.count(i) == 0) {
                cout << i << endl;
            }
        }

    }
    return 0;
}

Я не могу понять приведенный выше код. Пожалуйста, помогите мне понять это. Я просто не понимаю logi c за этой программой (я знаю STL, просто хочу понять logi c).

Answer 1

Это действительно очень просто. Вы предварительно вычисляете все простые числа, которые существуют в вашем диапазоне. Затем для каждого кратного простого числа, кроме первого, вы помечаете число как «не простое».

Выделенная строка просто вычисляет первое появление определенного кратного простого числа в диапазоне от M до N.

Изменить: Дополнительные объяснения.

Этот метод находит простые числа, сначала выполняя поиск всех не простых чисел. Остались простые числа.

Для этого на первом шаге вычисляются все "маленькие" простые числа. Затем для каждого малого штриха он отмечает все его кратные, которые попадают в целевой диапазон. Для этого вам нужно сначала вычислить первое появление этого простого числа в вашем диапазоне - это и есть переменная "start". В основном это первое кратное простому числу, которое> = M. Когда у вас есть "start", вы просто отмечаете все кратные числа, добавляя простое число к текущему числу, пока не достигнете N.

Если вы все еще не знаете, что и как "start" "вычисляется попробуйте подумать о том, как вы могли бы найти" x "так, чтобы это было" x = A * y "и" x> = M ", где вы знаете A и M, но не знаете" y ".

Также я думаю, что в этом алгоритме есть ошибка. Потому что он должен завершить этот цикл для каждого значения в "непростом" наборе. Но, может быть, это не имеет значения, если первое неучтенное простое кратное всегда> N.