Ninety-Nine Picat Problems

P2_01

Determine whether a given integer number is prime.

% isPrime(K) => prime(K).

prime(2) => true.
prime(3) => true.
prime(N),N > 3 =>
    foreach (I in 3..2..sqrt(N))
       N mod I != 0
    end.

P2_02

Determine the prime factors of a given positive integer.
Construct a flat list containing the prime factors in
ascending order.

primeFactors(N) = primeFactorsAux(N,2).

primeFactorsAux(N,F) = Res, F*F > N => Res = [N].
primeFactorsAux(N,F) = Res,
    N mod F == 0
=>
    Res = [F|primeFactorsAux(N div F,F)].
primeFactorsAux(N,F) = primeFactorsAux(N,F+1).

P2_03

Determine the prime factors of a given positive integer.

prime_factors_mult(N) = Res =>
    Pairs = primeFactors(N).encode(),         % see P1_10
    Res = [(I,Count) : (Count,I) in Pairs].

P2_04

A list of prime numbers.

Given a range of integers by its lower and upper limit,
construct a list of all prime numbers in that range.

primesR(A,B) = [P : P in primes(B), P >= A].

P2_05

Goldbach's conjecture.
Goldbach's conjecture says that every positive even number
greater than 2 is the sum of two prime numbers.
Example: 28 = 5 + 23.

goldbach(N) = first([(X,Y) : X in primesR(2, N-2), Y = N-X, prime(Y)]).

p2_06

A list of Goldbach compositions.

a) Given a range of integers by its lower and upper limit,
print a list of all even numbers and their Goldbach
composition.

b) In most cases, if an even number is written as the sum
of two prime numbers, one of them is very small. Very rarely,
the primes are both bigger than say 50. Try to find out how
many such cases there are in the range 2..3000.

goldbach_list(From,To) =>
    foreach(N in max(4,From)..To, even(N))
        (P1,P2) = goldbach(N),
        printf("%w = %w + %w\n",N,P1,P2)
    end.

goldbach_list_2(From,To,M) =>
    foreach(N in max(4,From)..To, even(N), (P1,P2) = goldbach(N), P1 >= M, P2 >= M)
        printf("%w = %w + %w\n",N,P1,P2)
    end.

P2_07

Determine the greatest common divisor of two positive
integer numbers. Use Euclid's algorithm.

myGCD(A,0) = abs(A).
myGCD(A,B) = myGCD(B, A mod B).

P2_08

Determine whether two positive integer numbers are coprime.
Two numbers are coprime if their greatest common divisor
equals 1.

coprime(A,B) => gcd(A,B) == 1.

P2_09

Calculate Euler's totient function phi(m).
Euler's so-called totient function phi(m) is defined as the
number of positive integers r (1 <= r < m) that are coprime
to m.

totient(N) = length([X : X in 1..N, coprime(X,N)]).

P2_10

Calculate Euler's totient function phi(m) (improved).

totient2(M) = prod([(P - 1) * P ** (C - 1) : (P, C) in prime_factors_mult(M)]).

P2_11

Compare the two methods of calculating Euler's totient
function.

% no code