How to resolve the algorithm Primality by trial division step by step in the GAP programming language

Published on 12 May 2024 09:40 PM
#Gap

How to resolve the algorithm Primality by trial division step by step in the GAP programming language

Table of Contents

Problem Statement

Write a boolean function that tells whether a given integer is prime.

Remember that   1   and all non-positive numbers are not prime. Use trial division. Even numbers greater than   2   may be eliminated right away. A loop from   3   to   √ n    will suffice,   but other loops are allowed.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Primality by trial division step by step in the GAP programming language

Source code in the gap programming language

IsPrimeTrial := function(n)
   local k, m;
   if n < 5 then
      return (n = 2) or (n = 3);
   fi;
   if RemInt(n, 2) = 0 then
      return false;
   fi;
   m := RootInt(n);
   k := 3;
   while k <= m do
      if RemInt(n, k) = 0 then
         return false;
      fi;
      k := k + 2;
   od;
   return true;
end;

Filtered([1 .. 100], IsPrimeTrial);                              
# [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 ]

You may also check:How to resolve the algorithm Accumulator factory step by step in the R programming language
You may also check:How to resolve the algorithm Determine if a string is collapsible step by step in the PL/M programming language
You may also check:How to resolve the algorithm General FizzBuzz step by step in the Factor programming language
You may also check:How to resolve the algorithm Floyd's triangle step by step in the Go programming language
You may also check:How to resolve the algorithm Loops/Break step by step in the Julia programming language