### Project Description

# Prolog Arithmetic and Operators

### a) Write a predicate to determine if a given integer is prime or not.

You do not need to worry about efficiency for this question. There are many sophisticated ways to find prime numbers but a simple brute force check will suffice.

?- prime(2). true. ?- prime(4). false. ?- prime(7). true. ?- prime(987). false. ?- prime(997). true. b) Write a predicate that finds the greatest common divisor of two positive integers.

Hint: Use Euclid’s algorithm. ?- gcd(6, 12, D). D = 6. ?- gcd(14, 21, D). D = 7. ?- gcd(1071, 462, D). D = 21. c) Write an infix operator =>> that returns true if one of its operands is double the other operand.

?- 40 =>> 20. true. ?- (-4) =>> (-8). true. ?- 1 =>> 0. false. ?- 3 =>> 7. false. d) Write a unary prefix operator isSingleton that determines if a list has exactly one element in it.

?- isSingleton []. false. ?- isSingleton [8]. true. ?- isSingleton [a,b]. false. e) Write two predicates isort and msort that sort a list of integers. The predicate isort should use the insertion sort method; this method starts with an empty list and inserts items one at a time into the correct position. The predicate msort should use the merge sort method. Merge sort splits a list into two halves, recursively sorts each half and then merges them back together. You should expect to write a number of support predicates for this question. ?- isort([7,3,5,4,1,2,6],[1,2,3,4,5,6,7]). true. ?- isort([7,3,5,4,1,2,6],I). I = [1, 2, 3, 4, 5, 6, 7]. ?- msort([4,5,3,2,2], M). M = [2, 2, 3, 4, 5].

2)You must put the following comments at the top of your program code and provide the appropriate information.

% Assignment number, 159.202, 2016 S2 % Family Name, Given Name, Student ID, % Explain what the program is doing . . . Hand-in: Submit your script electronically through stream

% Assignment number, 159.202, 2016 S2

% Family Name, Given Name, Student ID,

% Check if the number is prime

prime(X) :-

X \= 1, X \= 0,

X1 is X – 1,

prime(X, X1).

prime(_X, 1).

prime(_X, 0).

prime(X, N) :-

Mod is X mod N,

Mod \= 0,

N1 is N – 1,

prime(X, N1).

% test

:- include(prime, [1,2,3,4,5,6,7,8,9, 10,11,12,13,14,15,16,17,18,19,20], Xs)

, Xs = [2, 3, 5, 7, 11, 13, 17, 19].

% find greatest common divisor

gcd(A, A, A).

gcd(A, B, D) :-

A > B,

A1 is A – B,

gcd(A1, B, D).

gcd(A, B, D) :-

A < B,

B1 is B – A,

gcd(A, B1, D).

:- gcd(6, 12, 6).

:- gcd(14, 21, 7).

:- gcd(1071, 462, 21).

:- op(500, xfx, =>>).

% Check if one arg is twice as big as another

X =>> Y :-

X is Y * 2.

X =>> Y :-

Y is X * 2.

:- 40 =>> 20.

:- (-4) =>> (-8).

:- \+ (1 =>> 0).

:- \+ (3 =>> 7).

:- op(500, fx, isSingleton).

% check if list is a singleton

isSingleton [_].

:- \+ isSingleton [].

:- isSingleton [8].

:- \+ isSingleton [a,b].

% insertion sort

isort(Src, Dst) :-

% we insert each elem of Src into resulting list (which is initially [])

foldl(insert_ord, Src, [], Dst).

% trivial case

insert_ord(X, [], [X]).

% if current inserted X <= top Y, just prepend X to the list

insert_ord(X, [Y | Rest], [X, Y | Rest]) :-

X =< Y.

% otherwise insert X into the Rest producing Rest1 and prepend Y back

insert_ord(X, [Y | Rest], [Y | Rest1]) :-

X > Y,

insert_ord(X, Rest, Rest1).

:- isort([7,3,5,4,1,2,6],[1,2,3,4,5,6,7]).

% merge sort

%

% idea is: split list on two, recursively merge-sort both and merge the results

%

msort([], []).

msort([X], [X]).

msort(List, Sorted) :-

split(List, A, B), % split

maplist(msort, [A, B], [A1, B1]), % recure

merge(A1, B1, Sorted), % merge

!.

% split: [a,b,c,d,e,f,…] -> ([a,c,e,…], [b,d,f,…])

split(List, A, B) :- split(List, [], [], A, B).

split([], A, B, A, B).

split([X], A, B, [X | A], B).

split([X, Y | Rest], A, B, [X | AN], [Y | BN]) :-

split(Rest, A, B, AN, BN).

% merge two sorted lists into one sorted

merge(L, R, X) :- merge(L, R, [], X).

% if one or another is empty, the result is nonempty one

merge([], R, X, XN) :-

append(X, R, XN).

merge(L, [], X, XN) :-

append(X, L, XN).

% if one top is less than other, it goes first

merge([A | L], [B | R], X, XN) :-

A < B,

append(X, [A], X1),

merge(L, [B | R], X1, XN).

merge([A | L], [B | R], X, XN) :-

B =< A,

append(X, [B], X1),

merge([A | L], R, X1, XN).

:- msort([7,3,5,4,1,2,6],[1,2,3,4,5,6,7]).

### Project Details

**Date**November 3, 2016**Tags**Programming, Prolog and Clisp