почему итерация выполняется i + 6 каждый раз и почему условие i * i <= n для этой основной функции тестирования?

Question

https://www.geeksforgeeks.org/primality-test-set-1-introduction-and-school-method/

// Оптимизированная школьная методика на языке C ++ для проверки //, является ли число простым

#include <bits/stdc++.h> 
using namespace std; 

bool isPrime(int n) 
{ 
    // Corner cases 
    if (n <= 1)  return false; 
    if (n <= 3)  return true; 

    // This is checked so that we can skip  
    // middle five numbers in below loop 
    if (n%2 == 0 || n%3 == 0) return false; 

    for (int i=5; i*i<=n; i=i+6) 
        if (n%i == 0 || n%(i+2) == 0) 
           return false; 

    return true; 
}

Answer 1

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

for (int i=2; i < n; i=i+1) 
    if (n%i == 0)
       return false; 

Но это проверяет множество чисел, которые вам не нужнык.
Первое наблюдение (оптимизация) состоит в том, что любое кратное 2 (четное число) уже проверяется путем простого деления на 2 проверки один раз.

Так что теперь мы делаем проверку для 2, а затемпропускайте все остальные четные символы.

if (n%2 == 0 ) return false;

for (int i=3; i < n; i=i+2) 
    if (n%i == 0)
       return false; 

Следующее наблюдение (оптимизация) заключается в том, что вы можете сделать почти то же самое для трех.Итак, первый тест охватывает все комбинации 2 и 3.Теперь в цикле вы пропускаете каждые 6 чисел (2 * 3) и делаете некоторые тесты, чтобы охватить все числа, которые не кратны 2 или 3, которые происходят между ними.

if (n%2 == 0 || n%3 == 0) return false; 

for (int i=5; i<n; i=i+6) 
    if (n%i == 0 || n%(i+2) == 0) 
       return false; 

Так что это просто оптимизацияэто означает, что вам не нужно пробовать каждое число.

Следующее наблюдение, которое мы делаем, заключается в том, что вам не нужно пробовать числа, большие квадратного корня из n (они никогда не разделятся на n).Таким образом, вы можете ограничить цикл до i*i < n, так как i*i быстрее, чем sqrt(n).

if (n%2 == 0 || n%3 == 0) return false; 

for (int i=5; i*i<=n; i=i+6) 
    if (n%i == 0 || n%(i+2) == 0) 
       return false; 

Хотя лично я бы делал sqrt() один раз, а не i*i каждый раз вокруг цикла.Но это может быть медленнее для небольших значений n.

Answer 2

Любое составное число будет иметь хотя бы один фактор, который меньше или равен его квадратному корню. Зачем? Потому что, если он имеет только один фактор (кроме себя или одного), он будет равен его квадратному корню. Если у него два или более, самый маленький из них должен быть меньше его квадратного корня. Так что нет необходимости проверять числа больше квадратного корня - если бы оно не было простым, мы бы уже нашли коэффициент.

Код проверяет 2 или 3 как фактор на ранней стадии. После этого нам нужно только проверить факторы, которые не кратны двум или трем. Поэтому после проверки 5 и 7 нам не нужно проверять 6, 8, 9 или 10. Поэтому из каждых шести чисел нам нужно проверять только те два, которые не кратны двум или трем.