В данном тексте описан алгоритм работы программы поиска простых чисел, основанном на так называемом алгоритме просеивания чисел на решете Эратосфена. Вы можете скачать ее в разделе программы. Алгоритм реализован на языке С.

Рассмотрим саму программу:

    #include <stdio.h>
    #define N 20000
    //алгоритм "решето Эратосфена"
    unsigned int a[N];
    void main(){
       //заполним все ячейки числами по порядку: 0,1,2,3...
       for(int i=0; i<N; i++){
           a[i] = i;
       }
       //поскольку 1 не простое число, обнулим ячейку с этим числом
       a[1]=0;
       for(int s=2; s<N; s++){
           if(a[s]!=0){
               for(int j=s*2; j<N; j+=s){
                   a[j]=0;
               }
           }
       }
       for(i=0; i<<N; i++){
           if(a[i]!=0){
                printf("%d\n", a[i]);
           }
       }
    }

Приступим к описанию того, что в ней написано и что это означает.

Первая строка в программе предназначена для того, чтобы мы могли пользоваться стандартной функцией печати printf языка С.

    #include <stdio.h>

Сначала определим, что мы будем искать все простые числа не больше N, которое положим равным 20000. И сразу же заведем массив, где эти простые числа будем хранить:

    #define N 20000
    unsigned int a[N];

Заполним все его ячейки числами по порядку, начиная с 0 так: 0,1,2,3,... 20000

       for(int i=0; i<N; i++){
           a[i] = i;
       }

Суть метода состоит в том, что мы будем удалять все не простые числа из этого списка. То, что число, например 8 не является простым будет обозначено так, что в массиве на 8-ом месте находится 0, а не 8, как это было вначале. В массиве должны остаться только простые числа и потому массив будет выглядеть примерно так, как вторая строка в следующей таблице. Первая строка - это содержимое массива до обработки.

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,...
0, 0, 2, 3, 0, 5, 0, 7, 0, 0,  0, 11,...

Как же это сделать?

Во-первых, договоримся, что единица простым числом не является. Поэтому обнулим первый элемент массива:

       a[1]=0;

А теперь договоримся, что двойка - простое число. Почему это так, оставим за пределами обсуждения.

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

       for(int s=2; s<N; s++){
           if(a[s]!=0){
               for(int j=s*2; j<N; j+=s){
                   a[j]=0;
               }
           }
       }

Здесь s - это номер очередного числа. a[s] равно s, если оно простое и равно нулю, если оно не простое. Мы перебираем все числа от 2 до N и проверяем не простое ли оно, а именно a[s]!=0. Если это так то, начиная с числа s*2 и шагом s обнуляем все ячейки массива. Так обнулятся все числа, которые делятся на a[s]. И так цикл работает от 2 до N. После чего в массиве остаются только простые числа.

В конце программы мы их распечатываем, учитывая, что ячейки, в которых записан ноль, печатать не нужно:

       for(i=0; i<<N; i++){
           if(a[i]!=0){
                printf("%d\n", a[i]);
           }
       }

Вот и все. Надеюсь было понятно.