Все простые числа, кроме 2, нечетные, поэтому 2 становится самым нечетным простым числом.

78498 простых чисел меньше 10⁶

Эта статья разделена на две части

  1. Как определить, является ли число простым или нет
  2. Определение всех простых чисел меньше 10⁶

Как определить, является ли число N простым.

Это просто, если любое число от 2 до N-1 может делить N, тогда N не является простым.

#include<iostream>
using namespace std;
int main() {
    int N = 78;
    bool prime = true;
    for(int i=2;i<N;i++) {
        if(N%i == 0) {
            prime = false;
            break;
        }
    }
    if(prime) {
        cout<<N<<" is prime";
    } else {
        cout<<N<<" is not prime";
    }
    return 0;
}
Output:
78 is not prime
Time Complexity : O(N)

Можем ли мы улучшить сложность?

да. Посмотрим как.

Предположим, N = 30, давайте разбиваем это на 2 кратные

2 x 15 = 30
3 x 10 = 30
5 x  6 = 30
6 x 5 = 30
10 x 3 = 30
15 x 2 = 30

Если вы внимательно понаблюдаете и попробуете с другими числами, вы обнаружите, что эти кратные можно точно разделить пополам, 1-я половина является зеркалом 2-й половины. Нам не нужно проверять уже проверенные мультипликаторы.

Нам нужно только проверить до √N (потому что при √N предполагается, что 1-е и 2-е кратные должны быть равны)

#include<iostream>
#include<math.h>
using namespace std;
int main() {
    int N = 78;
    bool prime = true;
    for(int i=2;i<=sqrt(N);i++) {  // Observe <= sqrt(N)
        if(N%i == 0) {
            prime = false;
            break;
        }
    }
    if(prime) {
        cout<<N<<" is prime";
    } else {
        cout<<N<<" is not prime";
    }
    return 0;
}
Output:
78 is not prime
Time Complexity : O(√N)
This may not seem much, but we just reduced number of operations from 10^6 to 10^3

Найти все простые числа меньше 10⁶

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

Approach 1:
#include<iostream>
#include<math.h>
using namespace std;
int main() {
    bool prime[1000000];
    int N, count;
    for(N=2;N<1000000;N++) {
        bool isprime = true;
        for(int i=2;i<N;i++) {
            if(N%i == 0) {
                isprime = false;
                break;
            }
        }
        prime[N] = isprime;
        if(isprime) count++;
    }
    cout <<count<<endl;
}
Output: 78498
Complexity : O(N²)
Time Taken: 2 min 48 s

Оптимизированный код:

Approach 2:
#include<iostream>
#include<math.h>
using namespace std;
int main() {
    bool prime[1000000];
    int N, count;
    for(N=2;N<1000000;N++) {
        bool isprime = true;
        for(int i=2;i<=sqrt(N);i++) {
            if(N%i == 0) {
                isprime = false;
                break;
            }
        }
        prime[N] = isprime;
        if(isprime) count++;
    }
    cout <<count<<endl;
}
Output: 78498
Complexity : O(N√N)
Time Taken: 0.38s

от 2 мин 48 с → 0,38 с (менее секунды), поэтому важны оптимизация и знание сложности.

Можем ли мы улучшить ситуацию?

Да. Вы знаете о Сите Эратосфена. Давайте обсудим это.

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

В процессе, если мы встречаем число, которое не является кратным любому меньшему числу, тогда это простое число, и мы удаляем все кратные этого простого числа.

#include<iostream>
#include<cstring>
using namespace std;
int main() {
    int count = 0;
    bool prime[1000000];
    memset(prime, true, sizeof(prime)); // marking all as true
    for(int i=2;i<=1000000;i++){
        if(prime[i]==true) { // if not false yet, then it is prime
            for(int j=2;j*i<=1000000;j++) {
                prime[i*j]=false; // marking multiples of i as false
            }
            count++;
        }
    }
    cout<<count<<endl;
}
Output: 78498
Complexity: O(N log log N)
Time Taken: 0.024s

Понимание сложности:

N для внешнего цикла
N / 2 для кратных 2
N / 3 для кратных 3
N / 5 для кратных 5
….

Y = N + N / 2 + N / 3 + N / 4 + N / 5 + N / 6 + N / 7 + N / 8 + N / 9 + N / 10 +…
Y = N (1 + 1/2 + 1/3 + 1/4 + 1/5 +….
Y = N log N

но в фактическом уравнении не включены все термины, такие как N / 4, N / 6, N / 8, N / 9

При вычислении и математическом анализе он ограничен сверху N log log N. Если интересно, вы можете перейти по этим ссылкам здесь и здесь, чтобы прочитать более подробную информацию.

Сложность: O (N²) → O (N√N) → O (N log log N)
Время: 2мин 48с → 0,38с → 0,02с

Решето и простые числа широко используются в соревновательном программировании, и их очень важно хорошо понимать.

Связанная тема: Сегментированное решето (используется для поиска простых чисел еще более высоких диапазонов)