Решето Сундарама

Материал из Википедии — свободной энциклопедии

В математике решето́ Сундара́ма — детерминированный алгоритм нахождения всех простых чисел до некоторого целого числа . Разработан индийским студентом С. П. Сундарамом в 1934 году.

Содержание 1 Формализация алгоритма 2 Примеры реализации 2.1 Haskell 2.2 C++ 3 См. также 4 Ссылки

[править] Формализация алгоритма

Из ряда чисел от 1 до N исключаются все числа вида

где ,

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

Сложность этого алгоритма Θ(NlnN), что хуже, чем у решета Эратосфена Θ(NlnlnN).

[править] Примеры реализации

[править] Haskell

sundaram n = map (\x -> 2 * x + 1) $ filter (\y -> not $ y `elem` zs) [1..n] where 
        zs = [ i + j + 2 * i * j | i <- [1..n], j <- [1..i] ]

[править] C++

void sundaram(int n){
        int *a = new int [n], i, j, k;
        memset(a, 0, sizeof(int) * n);
        for(i = 1; 3*i+1 < n; i++){
                for(j = 1; (k = i+j+2*i*j) < n; j++){
                        a[k] = 1;
                }
        }
        for(i = 1; i < n; i++){
                if(a[i] == 0) cout << (2 * i + 1) << " ";
        }
        delete [] a;
}

[править] См. также

• Корекурсия
• Решето Эратосфена
• Решето Аткина

[править] Ссылки

• А. Б. Кордемский Математическая смекалка. — М.: ГИФМЛ, 1958.
• Решение С. П. Сундарама
• Формализация этого метода