Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Prolog
Перезагрузить страницу Решето Эратосфена
Ответ
 
Опции темы Опции просмотра
  (#31 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 8,033
Сказал(а) спасибо: 2
Поблагодарили 322 раз(а) в 321 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 25.05.2011, 19:31

Да. Так будет хорошо.
Ответить с цитированием
  (#32 (permalink)) Старый
oldpepper oldpepper вне форума
Member
 
Сообщений: 39
Сказал(а) спасибо: 9
Поблагодарили 2 раз(а) в 2 сообщениях
Регистрация: 24.05.2017
Адрес: С-Петербург
По умолчанию 08.05.2019, 02:55

Последняя программа Alison пропускает некоторые составные числа. Третье предложение предиката strike_out признает простым число без какой-либо проверки. Я думаю, что более правильным и близким к алгоритму Решета Эратосфена будет следующий вариант:

Visual Prolog Код:
class predicates
    prime : (unsigned, unsigned* [out]) determ.
clauses

    prime(N, PrimeList) :-
        list_of_numbers(2, N, Xs),
        sieve(Xs, PrimeList).

class predicates   %   Создает список чисел от C до N.
    list_of_numbers : (unsigned, unsigned, unsigned* [out]).
clauses

    list_of_numbers(X, N, [X | Xt]) :-
        X <= N, !,
        X1 = X + 1,
        list_of_numbers(X1, N, Xt).
    list_of_numbers(_, _, []).

class predicates   %   Решето
    sieve : (unsigned*, unsigned* [out]) determ.
clauses

    sieve([Xh | Xt],  [Xh | Zs]) :-
        strike_out(Xh, Xh, Xt, Ys),
        sieve(Ys, Zs).
    sieve([],  []).

class predicates   %   Вычеркивание чисел из списка
    strike_out : (unsigned, unsigned, unsigned*, unsigned* [out]).
clauses

    strike_out(X, A, [X | Xt], Ys) :- !,
        X1 = X + A,
        strike_out(X1, A, Xt, Ys).

    strike_out(X, A, [Xh | Xt], Ys) :-
        X < Xh, !,
        X1 = X + A,
        strike_out(X1, A, [Xh | Xt], Ys).

    strike_out(X, A, [Xh | Xt], [Xh | Ys]) :-
        strike_out(X, A, Xt, Ys).

    strike_out(_, _, [], []).
Ответить с цитированием
  (#33 (permalink)) Старый
oldpepper oldpepper вне форума
Member
 
Сообщений: 39
Сказал(а) спасибо: 9
Поблагодарили 2 раз(а) в 2 сообщениях
Регистрация: 24.05.2017
Адрес: С-Петербург
По умолчанию 08.05.2019, 10:58

Далее реализацию базового алгоритма можно пооптимизировать. Самое очевидное, это использовать решето по нечетным числам и выполнять просеивание только до корня. Реализация strike_out остается без изменений. Остальное будет выглядеть примерно так:

Visual Prolog Код:
class predicates
    prime : (unsigned, unsigned* [out]) determ.
clauses

    prime(N, [2 | PrimeList]) :-
        list_of_numbers(3, N, Xs),
        sieve(N, Xs, PrimeList).

class predicates  %  Создает список чисел от C до N с шагом 2.
    list_of_numbers : (unsigned, unsigned, unsigned* [out]).
clauses

    list_of_numbers(X, N, [X | Xt]) :-
        X <= N, !,
        X1 = X + 2,
        list_of_numbers(X1, N, Xt).
    list_of_numbers(_, _, []).

class predicates   %   Решето
    sieve : (unsigned, unsigned*, unsigned* [out]) determ.
clauses

    sieve(N, [Xh | Xt],  [Xh | Zs]) :-
        Xh * Xh <= N, !,
        strike_out(Xh, Xh, Xt, Ys),
        sieve(N, Ys, Zs).
    sieve(_, Xs, Xs).
Ответить с цитированием
  (#34 (permalink)) Старый
oldpepper oldpepper вне форума
Member
 
Сообщений: 39
Сказал(а) спасибо: 9
Поблагодарили 2 раз(а) в 2 сообщениях
Регистрация: 24.05.2017
Адрес: С-Петербург
По умолчанию 08.05.2019, 12:53

Использование в исходном списке только нечетных чисел сокращает его в два раза. Можно применить более сложный вариант. Следующий предикат list_of_numbers генерирует список, исключая из него числа кратные 2,3,5 и 7. Это уменьшает его приблизительно в пять раз.

Visual Prolog Код:
class predicates
    list_of_numbers : (unsigned, unsigned* [out]).
    list_of_numbers7 : (unsigned, unsigned, unsigned, unsigned, unsigned, unsigned* [out]).
    numberlist7 : (unsigned, unsigned, unsigned, unsigned, unsigned, unsigned, unsigned* [out]).
clauses

    list_of_numbers(N, Zs) :-
        list_of_numbers7(N, 7, 1, 3, 5, Zs).

    list_of_numbers7(N, X, A, B, C, Zs) :-
        numb5(A, B, C, A1, B1, C1, X1),
        X1 <= N, !,
        numberlist7(N, X, A1, B1, C1, X1, Zs).

    list_of_numbers7(_, _, _, _, _, []).

    numberlist7(N, X, A, B, C, X1, Zs) :-
        X = X1, !,
        Y = X + 7,
        list_of_numbers7(N, Y, A, B, C, Zs).

    numberlist7(N, X, A, B, C, X1, Zs) :-
        X < X1, !,
        Y = X + 7,
    numberlist7(N, Y, A, B, C, X1, Zs).

    numberlist7(N, X, A, B, C, X1, [Zh | Zt]) :-
        Zh = X1,
        list_of_numbers7(N, X, A, B, C, Zt).

class predicates
    numb5 : (unsigned, unsigned, unsigned, unsigned [out], unsigned [out], unsigned [out], unsigned [out]).
    numb3 : (unsigned, unsigned, unsigned [out], unsigned [out], unsigned [out]).
clauses

    numb5(A, B, C, A2, B2, C2, Z) :-
        numb3(A, B, A1, B1, X),
        if C = X then
            C1 = C + 5,
            numb5(A1, B1, C1, A2, B2, C2, Z)
        elseif C < X then
            C1 = C + 5,
            numb5(A, B, C1, A2, B2, C2, Z)
        else
            Z = X, A2 = X, B2 = B1, C2 = C
        end if.

    numb3(A, B, A2, B2, Z) :-
        X = A + 2,
        if  B = X then
            B1 = B + 3,
            numb3(X, B1, A2, B2, Z)
        elseif B < X then
            B1 = B + 3,
            numb3(A, B1, A2, B2, Z)
        else
            Z = X, A2 = Z, B2 = B
        end if.

Последний раз редактировалось oldpepper; 08.05.2019 в 12:54 Причина: синтаксическая ошибка
Ответить с цитированием
  (#35 (permalink)) Старый
oldpepper oldpepper вне форума
Member
 
Сообщений: 39
Сказал(а) спасибо: 9
Поблагодарили 2 раз(а) в 2 сообщениях
Регистрация: 24.05.2017
Адрес: С-Петербург
По умолчанию 09.05.2019, 19:24

Ну и последняя модификация - блочное решето Эратосфена с "прореженным" исходным списком. Простые числа выдает достаточно быстро и много.

Visual Prolog Код:
class predicates
    prime : (unsigned, unsigned* [out]) determ.
    primtail : (unsigned, unsigned, unsigned, unsigned, unsigned, unsigned, unsigned,  unsigned*, unsigned* [out]) determ.
clauses

    prime(N, [2,3,5,7 | PrimList]) :-
            % Определить параметры для блочной генерации
        SqN = roundToUnsigned(sqrt(convert(uReal, N))),
        % Величина блока
        M = if N - SqN * Sqn > 0 then SqN + 1 else Sqn end if,
            % Генерировать исходный список для первого блока
        list_of_numbers7(M, 7, 1, 3, 5, X, A, B, C, Xs),
            % Получить список простых чисел первого блока
        sieve(M, Xs, PLst1),
            % Обработать оставшиеся блоки
        primtail(N, M, M+M, X, A, B, C, PLst1, PrimTail),
        PrimList = append(PLst1, PrimTail).

    primtail(N, M, N1, X, A, B, C, PLst1, PrimList) :-
        N1 <= N, !,
        N2 = if N1+M > N then N else N1 end if,
            % Генерировать исходный список для очередного блока
        list_of_numbers7(N2, X, A, B, C, X2, A2, B2, C2, Xs),
            %  Используя список простых чисел первого блока получить список простых чисел текущего блока
        blocksieve(N, Xs, PLst1, PLstN),
            % Обработать очередной блок
        primtail(N, M, N1+M, X2, A2, B2, C2, PLst1, PrimTail),
        PrimList = append(PLstN, PrimTail).

    primtail(_, _, _, _, _, _, _, _, []).

class predicates
    list_of_numbers7 : (unsigned, unsigned, unsigned, unsigned, unsigned,
                unsigned [out], unsigned [out], unsigned [out], unsigned [out], unsigned* [out]) determ.
    numblist7 : (unsigned, unsigned, unsigned, unsigned, unsigned, unsigned, unsigned, unsigned, unsigned,
                unsigned [out], unsigned [out], unsigned [out], unsigned [out], unsigned* [out]) determ.
clauses

    list_of_numbers7(N, X, A, B, C, X2, A2, B2, C2, Zs) :-
        numb5(A, B, C, A1, B1, C1, X1),
        numblist7(N, X, A, B, C, X1, A1, B1, C1, X2, A2, B2, C2, Zs).

    numblist7(N, X, A, B, C, X1, A1, B1, C1, X2, A2, B2, C2, Zs) :-
        if X1 <= N then
            X = X1, !,
            list_of_numbers7(N, X+7, A1, B1, C1, X2, A2, B2, C2, Zs)
        else
            X2 = X, !,
            A2 = A, B2 = B, C2 = C, Zs = []
        end if.

    numblist7(N, X, A, B, C, X1, _, _, _, X2, A2, B2, C2, Zs) :-
            X < X1, !,
            list_of_numbers7(N, X+7, A, B, C, X2, A2, B2, C2, Zs).

    numblist7(N, X, _, _, _, X1, A1, B1, C1, X2, A2, B2, C2, [X1 | Zt]) :-
            list_of_numbers7(N, X, A1, B1, C1, X2, A2, B2, C2, Zt).

class predicates
    numb5 : (unsigned, unsigned, unsigned, unsigned [out], unsigned [out], unsigned [out], unsigned [out]).
    numb3 : (unsigned, unsigned, unsigned [out], unsigned [out], unsigned [out]).
clauses

    numb5(A, B, C, A2, B2, C2, Z) :-
        numb3(A, B, A1, B1, X),
        if C = X then
            numb5(A1, B1, C+5, A2, B2, C2, Z)
        elseif C < X then
            numb5(A, B, C+5, A2, B2, C2, Z)
        else
            Z = X, A2 = X, B2 = B1, C2 = C
        end if.

    numb3(A, B, A2, B2, Z) :-
        X = A + 2,
        if  B = X then
            numb3(X, B+3, A2, B2, Z)
        elseif B < X then
            numb3(A, B+3, A2, B2, Z)
        else
            Z = X, A2 = Z, B2 = B
        end if.

class predicates   %   Решето
    blocksieve : (unsigned, unsigned*, unsigned*, unsigned* [out]) determ.
clauses

    blocksieve(N, [Xh | Xt], [Ph | Pt], Zs) :-
        Dv = Xh div Ph,
        X1 = Ph * Dv,
        strike_out(X1, Ph, [Xh | Xt], Ys),
        blocksieve(N, Ys, Pt, Zs).

    blocksieve(_, Xs, [], Xs).

class predicates   %   Решето
    sieve : (unsigned, unsigned*, unsigned* [out]) determ.
clauses

    sieve(N, [Xh | Xt],  [Xh | Zs]) :-
        Xh * Xh <= N, !,
        strike_out(Xh, Xh, Xt, Ys),
        sieve(N, Ys, Zs).
    sieve(_, Xs, Xs).

class predicates   %   Вычеркивание чисел из списка
    strike_out : (unsigned, unsigned, unsigned*, unsigned* [out]).
clauses

    strike_out(X, A, [X | Xt], Ys) :- !,
        strike_out(X+A, A, Xt, Ys).

    strike_out(X, A, [Xh | Xt], Ys) :-
        X < Xh, !,
        strike_out(X+A, A, [Xh | Xt], Ys).

    strike_out(X, A, [Xh | Xt], [Xh | Ys]) :-
        strike_out(X, A, Xt, Ys).

    strike_out(_, _, [], []).

Последний раз редактировалось oldpepper; 09.05.2019 в 19:28 Причина: Ошибка
Ответить с цитированием
Ads.
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.




Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов