How to resolve the algorithm Sequence of primes by trial division step by step in the ALGOL-M programming language

Published on 12 May 2024 09:40 PM
#Algol-m

How to resolve the algorithm Sequence of primes by trial division step by step in the ALGOL-M programming language

Table of Contents

Problem Statement

Generate a sequence of primes by means of trial division.

Trial division is an algorithm where a candidate number is tested for being a prime by trying to divide it by other numbers. You may use primes, or any numbers of your choosing, as long as the result is indeed a sequence of primes. The sequence may be bounded (i.e. up to some limit), unbounded, starting from the start (i.e. 2) or above some given value. Organize your function as you wish, in particular, it might resemble a filtering operation, or a sieving operation. If you want to use a ready-made is_prime function, use one from the Primality by trial division page (i.e., add yours there if it isn't there already).

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Sequence of primes by trial division step by step in the ALGOL-M programming language

Source code in the algol-m programming language

BEGIN

INTEGER I, K, M, N, S, NPRIMES, DIVISIBLE, FALSE, TRUE;

COMMENT COMPUTE P MOD Q; 
INTEGER FUNCTION MOD (P, Q);
INTEGER P, Q;
BEGIN
  MOD := P - Q * (P / Q);
END;

COMMENT MAIN PROGRAM BEGINS HERE;

WRITE ("HOW MANY PRIMES DO YOU WANT TO GENERATE?");
READ (NPRIMES);
  BEGIN
    INTEGER ARRAY P[1:NPRIMES];
    FALSE := 0;
    TRUE := -1;

    % INITIALIZE P WITH FIRST (AND ONLY EVEN) PRIME NUMBER %
    P[1] := 2;
    WRITE (1, ":", P[1]);

    I := 1;  % COUNT OF PRIME NUMBERS FOUND SO FAR %
    K := 1;  % INDEX OF LARGEST PRIME <= SQRT OF N %
    N := 3;  % CURRENT NUMBER BEING CHECKED %
    WHILE I < NPRIMES DO
      BEGIN
        S := P[K] * P[K];
        IF S <= N THEN K := K + 1;
        DIVISIBLE := FALSE;
        M := 2;  % INDEX OF POSSIBLE DIVISORS (EXCLUDING 2) %
        WHILE M <= K AND DIVISIBLE = FALSE DO
          BEGIN
            IF MOD(N, P[M]) = 0 THEN DIVISIBLE := TRUE;
            M := M + 1;
          END;
        IF DIVISIBLE = FALSE THEN
          BEGIN
            I := I + 1;
            P[I] := N;
            WRITE (I, ":", N);
          END;
        N := N + 2;
      END;  
  END;

END

You may also check:How to resolve the algorithm Loops/Break step by step in the Frink programming language
You may also check:How to resolve the algorithm Write float arrays to a text file step by step in the Fortran programming language
You may also check:How to resolve the algorithm Function definition step by step in the ooRexx programming language
You may also check:How to resolve the algorithm Wasteful, equidigital and frugal numbers step by step in the F# programming language
You may also check:How to resolve the algorithm Thiele's interpolation formula step by step in the Go programming language