C оптимизация программы/увеличение скорости

Question

В качестве новичка я сделал программу, которая находит количество простых чисел (prime), которые не превышают входное натуральное число (x). Программа работает отлично (я думаю), но я хочу, чтобы она работала быстрее (для более высоких чисел). Возможно ли, и если да, то как?

#include <stdio.h> 

int main() { 
    int x, i, j, flag = 1, prime = 0 ; 

    scanf("%d", &x); 
    for (i = 2; i <= x; i++) { 
     j = 2; 
     while (flag == 1 && j < i/2 + 1) { 
      if (i % j == 0) { 
       flag = 0; 
      } 
      j++; 
     } 
     if (flag == 1) { 
      prime++; 
     } 
     flag = 1; 
    } 
    printf("%d\n", prime); 
    return 0; 
} 

Answer 1

Ваш алгоритм выполняет пробное деление, которое происходит медленно. Лучший алгоритм является 2000-летний Решето Эратосфена:

function primes(n): 
    sieve := makeArray(2..n, True) 
    for p from 2 to n 
     if sieve[p] 
      output p # prime 
      for i from p*p to n step p 
       sieve[i] := False 

Я оставлю его вам перевести C. Если вы хотите узнать больше, я скромно рекомендую эссе Programming with Prime Numbers в моем блоге.

Answer 2

Существует одна известная теорема о простых числах. В нем указывается, что

π(n)≈n/ln(n) 

Но существуют определенные алгоритмы для вычисления этой функции. Следуйте ссылкам: PNT

Computing π(x): The Meissel, Lehmer, Lagarias, Miller, Odlyzko method