Почему этот алгоритм с простым числом работает?

Question

#define _CRT_SECURE_NO_WARNINGS 

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

int main() { 
    int anz; 
    scanf("%d", &anz); 
    time_t start = time(0); 
    int *primZ = malloc(anz * sizeof(int)); 
    primZ[0] = 2; 
    int Num = 0; 

    for (int i = 1, num = 3; i < anz; num += 2) { 
     for (int j = 1; j < i; j++) { 
      if (num % primZ[j] == 0) { 
       num += 2; 
       j = 0; 
      } 

      //this part 
      if (primZ[j] > i/2) 
       break; 
     } 

     primZ[i] = num; 
     i++; 
     printf("%d ,",num); 
    } 

    time_t delta = time(0) - start; 
    printf("%d", delta); 
    getchar(); 
    getchar(); 
    return 0; 
} 

Код работает отлично, вопрос в том, почему. Часть if(primZ[j] > i/2) делает программу в 2 - 3 раза быстрее. На самом деле это было if(primZ[j] > num/3), что имеет прекрасный смысл, потому что num может быть нечетным числом. Но это число найденных простых чисел. Это не имеет никакого смысла для меня. Пожалуйста, объясни.

Answer 1

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

Например, 33 является составным, но вам нужно только проверять числа до 5, чтобы понять, что вам не нужно проверять его делимость на 11, потому что он оставляет 3 (33/11 = 3), которые мы уже проверено.

Это означает, что вы могли бы улучшить свой алгоритм,

for (int j = 1; j < i; j++) { 
     if(primZ[j]*primZ[j] > num) 
      break; 

     if (num % primZ[j] == 0) { 
      num += 2; 
      j = 0; 
     } 
    } 

Причины вы можете уйти с сравнением с резкой на i/2 обусловлено распределение простых чисел. Основная функция подсчета составляет приблизительно i = num/log(num), а затем вы получаете i/2 > sqrt(num).

Answer 2

Это имеет смысл, так как если п имеет два фактора, один из них, безусловно, меньше или равна п/2, толку программа не нашла факторов i в primZ, которые меньше или равны i/2 это не означает, что есть нет факторы i -except 1, конечно.

primZ Чувство сортируются в порядке возрастания и J только увеличивается, когда primeZ[j] > i/2 это указывает на то, что нет никаких факторов i в primZ, которые меньше, чем I/2.

PSThe точка начала поиска говорится в первой части для постановки num=3, и повторяющееся утверждение num += 2 гарантирует, что вы только проверить нечетные номера

Answer 3

Причина заключается в том, что фактическая граница гораздо сильнее, чем num/3 - вы можете использовать:

if (primZ[j] > sqrt(num)) 

Причина что в том, что если простое выше, чем квадратный корень из num делит num, там также должно быть нижним числом, которое делает (так как результат такого деления должен быть меньше квадратного корня).

Это означает, что до тех пор, пока i/2 выше sqrt(num), код будет работать. Случается, что число простых чисел ниже числа растет быстрее, чем квадратный корень этого числа, что означает, что (совершенно случайно) i/2 является надежной гарантией использования.

Вы можете проверить, как ваше значение i ведет себя here - они называют это pi (x), число простых чисел меньше x.