How to resolve the algorithm Lucas-Lehmer test step by step in the Seed7 programming language

Problem Statement
Step by Step Solution
Sourcecode

Problem Statement

Lucas-Lehmer Test: for

{\displaystyle p}

an odd prime, the Mersenne number

− 1

{\displaystyle 2^{p}-1}

is prime if and only if

− 1

{\displaystyle 2^{p}-1}

divides

S ( p − 1 )

{\displaystyle S(p-1)}

where

S ( n + 1 )

( S ( n )

)

− 2

{\displaystyle S(n+1)=(S(n))^{2}-2}

, and

S ( 1 )

{\displaystyle S(1)=4}

Calculate all Mersenne primes up to the implementation's maximum precision, or the 47th Mersenne prime (whichever comes first).

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Lucas-Lehmer test step by step in the Seed7 programming language

Source code in the seed7 programming language

$ include "seed7_05.s7i";
  include "bigint.s7i";
 
const func boolean: isPrime (in integer: number) is func
  result
    var boolean: prime is FALSE;
  local
    var integer: upTo is 0;
    var integer: testNum is 3;
  begin
    if number = 2 then
      prime := TRUE;
    elsif number rem 2 = 0 or number <= 1 then
      prime := FALSE;
    else
      upTo := sqrt(number);
      while number rem testNum <> 0 and testNum <= upTo do
        testNum +:= 2;
      end while;
      prime := testNum > upTo;
    end if;
  end func;

const func boolean: lucasLehmerTest (in integer: p) is func
  result
    var boolean: prime is TRUE;
  local
    var bigInteger: m_p is 0_;
    var bigInteger: s is 4_;
    var integer: i is 0;
  begin
    if p <> 2 then
      m_p := 2_ ** p - 1_;
      for i range 2 to pred(p) do
        s := (s ** 2 - 2_) rem m_p;
      end for;
      prime := s = 0_;
    end if;
  end func;

const proc: main is func
  local
    var integer: p is 2;
  begin
    writeln(" Mersenne primes:");
    while p <= 3217 do
      if isPrime(p) and lucasLehmerTest(p) then
        write(" M" <& p);
        flush(OUT);
      end if;
      incr(p);
    end while;
    writeln;
  end func;