Решето Аткина (Реализация на С++)

C++   13 Июнь 2012  Автор статьи:  

Программа выводит в консоль все простые числа из диапазона [1, 10000].
Реализация данного алгоритма на С++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <math.h>
#include <ctime>
using namespace std;
int main()
{
    int limit = 10001;
    int sqr_lim;
    bool is_prime[10002];
    int x2, y2;
    int i, j;
    int n;
    sqr_lim = (int)sqrt((long double)limit);
    for (i = 0; i <= limit; i++)
        is_prime[i] = false; // Инициализация решета
    is_prime[2] = true;
    is_prime[3] = true;
// Предположительно простые - это целые с нечетным числом
// представлений в данных квадратных формах.
// x2 и y2 - это квадраты i и j (оптимизация).
    x2 = 0;
    for (i = 1; i <= sqr_lim; i++)
    {
        x2 += 2 * i - 1;
        y2 = 0;
        for (j = 1; j <= sqr_lim; j++)
        {
            y2 += 2 * j - 1;
            n = 4 * x2 + y2;
            if ((n <= limit) && (n % 12 == 1 || n % 12 == 5))
                is_prime[n] = !is_prime[n];
            // n = 3 * x2 + y2;
            n -= x2; // Оптимизация
            if ((n <= limit) && (n % 12 == 7))
                is_prime[n] = !is_prime[n];
            // n = 3 * x2 - y2;
            n -= 2 * y2; // Оптимизация
            if ((i > j) && (n <= limit) && (n % 12 == 11))
                is_prime[n] = !is_prime[n];
        }
    }
// Отсеиваем кратные квадратам простых чисел в интервале [5, sqrt(limit)].
// (основной этап не может их отсеять)
    for (i = 5; i <= sqr_lim; i++)
    {
        if (is_prime[i])
        {
            n = i * i;
            for (j = n; j <= limit; j += n)
            {
                is_prime[j] = false;
            }
        }
    }
// Вывод списка простых чисел в консоль.
    printf("2 3 5");
    for (i = 6; i <= limit; i++) // проверка делимости на 3 и 5
    {
        if ((is_prime[i]) && (i % 3 != 0) && (i % 5 != 0))
        {
            printf(" %d", i);
        }
    }
    cin>>n;
}

Научиться программировать

  • на Delphi

  • на Java

  • на C++