The germ for this post is from a question that was asked in an interview. This person, a self confessed RPG "fresher", had been asked to write a "RPG free" program to calculate the prime numbers between 1 and 11. This request intrigued me, and made me think what kind of program the interviewer probably wanted, and what I would write if I need to use this at work.

Let me start with the basics, the definition of what is a prime number:

Any integer other than 0 or 1 that is not divisible without remainder by any other integers except 1 and the integer itself

Taken from the Merriam Webster dictionary.

What are the prime numbers in the desired range:

2, 3, 5, 7, 11

First let me show the program I would have written if I had been in this interview.

01 **free 02 dcl-c MaxRange const(11) ; 03 dcl-s Number packed(3) ; 04 dcl-s Divisor like(Number) ; 05 dcl-s Text char(20) ; 06 for Number = 2 to MaxRange ; 07 Text = ' ' ; 08 for Divisor = 2 to (Number - 1) ; 09 if (%rem(Number:Divisor) = 0) ; 10 Text = %char(Number) + ' not prime' ; 11 leave ; 12 endif ; 13 endfor ; 14 if (Text = ' ') ; 15 Text = %char(Number) + ' is prime' ; 16 endif ; 17 dsply Text ; 18 endfor ; 19 *inlr = *on ; |

Line 1: They wanted a "RPG free" program so this is going to be one.

Line 2: This is the free format definition for a constant. I am using this constant as the maximum number I will check if it is a prime number. The request was for 1 – 11, therefore, this constant contains the value of 11. I made this a constant as if I need to change the maximum number in the range then I could just change this.

Lines 3 – 5: Definitions of the variables I will be using.

Line 6: I always prefer to use a FOR group when I need to loop and increment values. In this example I am initializing the variable `Number` with 2, as I have not given a value to increment 1 is assumed, to the value of the constant `MaxRange` which is 11.

Line 8: A second FOR group. This time it is the `Divisor`, the number the variable `Number` is divide by, that is being incremented. It is initialized with 2, incrementing is assumed as 1, to the value of `Number` minus 1. Why to `Number` - 1? I don't need to perform the calculation of dividing the number by itself, therefore, I want to stop looping before I get to the value of `Number`.

Line 9: What I love about Built in Functions is that I can use them in a `IF` statement. In this case I am using the `%REM` built in function and if the remainder returned is zero then the `Number` tested is not a prime, and `Text` is updated with a string to say that the tested number is not a prime.

Line 14: By the time the logic reaches here either the number tested is not a prime, `Text` is not blank, or the program has performed the check of remainder with every necessary divisor, `Text` is blank so the number must be a prime.

Line 17: I display the string in `Text`.

Line 18: This `ENDFOR` corresponds to the `FOR` that began on line 6, `Number` is incremented by 1, and the test of remainder is repeated with this new number.

When I run the program the output on my screen looks like:

DSPLY 2 is prime DSPLY 3 is prime DSPLY 4 not prime DSPLY 5 is prime DSPLY 6 not prime DSPLY 7 is prime DSPLY 8 not prime DSPLY 9 not prime DSPLY 10 not prime DSPLY 11 is prime |

Perfect results from a program simple enough for any interviewer.

Now if I was doing this for my own use in a business environment I would place the logic into an external procedure. I am going to give two example procedures. The first is the equivalent of the above program, and the second was another way I came up with reduce the number of checks of remainders I will need to do.

I placed both of the procedures into the same source member. The "global" area, common to all the procedures, in this member looks like:

01 **free 02 ctl-opt nomain ; 03 /define IsItPrime1 04 /define IsItPrime2 05 /include devsrc,copybook 06 /undefine IsItPrime1 07 /undefine IsItPrime2 |

Line 2: I need to use the `NOMAIN` control option so that the compiler knows that this procedure does not have a main procedure. Which it will not as the procedures in this source members will be called from other programs and procedures.

Lines 3, 4, 6, and 7: These are the compiler directives I must have to include only those procedure prototypes relevant to procedures in this source member. If I `/DEFINE` I always `/UNDEFINE`, it is not required just one of those things I feel I must do.

Line 5: `/INCLUDE` includes the relevant sections of code from the source member `COPYBOOK` when this member is compiled.

The first procedure that is similar to my previous program looks like:

08 dcl-proc IsItPrime1 export ; 09 dcl-pi *n char(1) ; 10 inNumber packed(3) const ; 11 end-pi ; 12 dcl-s Divisor uns(5) ; 13 if (inNumber < 2) ; 14 return 'E' ; 15 endif ; 16 for Divisor = 2 to (inNumber - 1) ; 17 if (%rem(inNumber:Divisor) = 0) ; 18 return 'N' ; 19 endif ; 20 endfor ; 21 return 'Y' ; 22 end-proc ; |

Line 8: Start of the procedure. As this procedure will be exporting it results to other programs, modules, etc I need the `EXPORT` keyword after the procedure name.

Lines 9 - 11: I never bother to name my procedure interfaces, `*N` will do. A 3,0 packed parameter is passed to this procedure, line 10, and I use the `CONST` keyword to make this variable "read only", in other words I cannot change the value that is passed back to the calling program. The procedure returns a 1 character value, which is what the `CHAR(1)` on line 9 stands for.

Lines 13 – 15: As 1, zero, and negative numbers cannot be primes if the passed number is less than 2 then it is an "Error".

Lines 16 – 20: This is the same logic I used in the interview program to determine if the number is prime.

Line 21: If I have reached this point then I know that the number is a prime.

Then I started thinking about the numbers I was using as the divisor. I only need to check the remainder with prime numbers in the divisor, because if the number was not divisible by 2 it was not going to be divisible by 4, 6, 8, etc. So I created a second procedure using this method.

23 dcl-proc IsItPrime2 export ; 24 dcl-pi *n char(1) ; 25 inNumber packed(3) const ; 26 end-pi ; 27 dcl-ds *n ; 28 *n packed(3) inz(2) ; 29 *n packed(3) inz(3) ; 30 *n packed(3) inz(5) ; 31 *n packed(3) inz(7) ; 32 *n packed(3) inz(11) ; 33 *n packed(3) inz(13) ; 34 *n packed(3) inz(17) ; 35 *n packed(3) inz(19) ; 36 *n packed(3) inz(23) ; 37 *n packed(3) inz(29) ; 38 *n packed(3) inz(31) ; 39 *n packed(3) inz(37) ; 40 *n packed(3) inz(41) ; 41 *n packed(3) inz(43) ; 42 *n packed(3) inz(47) ; 43 *n packed(3) inz(53) ; 44 *n packed(3) inz(59) ; 45 *n packed(3) inz(61) ; 46 *n packed(3) inz(67) ; 47 *n packed(3) inz(71) ; 48 *n packed(3) inz(73) ; 49 *n packed(3) inz(79) ; |

This is almost the same as my previous procedure, except...

Lines 27 – 55: I need an array of prime numbers, in this case from 2 – 100. The quickest way I could think to load an array with these values was to use a data structure, and then define an array to overlay the data structure's subfields, line 54. Notice that I did not give the data structure a name, I just gave it `*N` instead, which means it is nameless. The data structure subfields are also unnamed.

Lines 57 and 58: If the passed number is less than 2 it is an error.

Lines 59 - 65: If the passed number is less or equal to 100, then it is looked up in the array. If it is found return 'Y' as it is a prime, if it is not found return 'N'.

Lines 67 – 72: If the passed number is greater than 100 I do the same as I did in the interview program and the previous procedure, but using the prime numbers from the array only. If I find that remainder is 0 then it is not a prime, and return 'N'.

Line 73: I only reach here if the number is not, not a prime. By returning 'Y' it says that the number is a prime.

Now I have to define the procedure prototypes in the copybook member, `COPYBOOK`.

01 **free 02 /if defined(IsItPrime1) 03 //Values returned E = Error, number less than 2 04 // N = Not a prime number 05 // Y = Is a prime number 06 dcl-pr IsItPrime1 char(1) ; 07 *n packed(3) const ; 08 end-pr ; 09 /endif 10 /if defined(IsItPrime2) 11 //Values returned E = Error, number less than 2 12 // N = Not a prime number 13 // Y = Is a prime number 14 dcl-pr IsItPrime2 char(1) ; 15 *n packed(3) const ; 16 end-pr ; 17 /endif |

Lines 2 and 10: If the program or procedure has a `/DEFINE` that matches the tag in the `/IF` then the code between the `/IF` and its matching `/ENDIF` will be included into what is being compiled. In this code each snippet contains the procedure interface information for the procedures I have just created.

I compile the source member containing the procedures into a module.

CRTRPGMOD MODULE(MYLIB/PRIMESMOD) SRCFILE(MYLIB/DEVSRC) OPTION(*SRCSTMT) DBGVIEW(*ALL) ALWNULL(*YES) |

And add the module to my binding directory.

ADDBNDDIRE BNDDIR(MYLIB/BNDDIR) OBJ((PRIMESMOD *MODULE)) |

Last piece is a program to call these two procedures.

01 **free 02 ctl-opt option(*srcstmt) bnddir('BNDDIR') ; 03 /define IsItPrime1 04 /define IsItPrime2 05 /include devsrc,copybook 06 /undefine IsItPrime1 07 /undefine IsItPrime2 08 dcl-s Count packed(3) ; 09 dcl-s RtnChar char(1) ; 10 for Count = 1 to 11 ; 11 RtnChar = IsItPrime1(Count) ; 12 if (RtnChar = 'N') ; 13 dsply ('1: ' + %char(Count) + ' not prime') ; 14 elseif (RtnChar = 'Y') ; 15 dsply ('1: ' + %char(Count) + ' prime') ; 16 elseif (RtnChar = 'E') ; 17 dsply ('1: ' + %char(Count) + ' cannot be prime') ; 18 endif ; 19 endfor ; 20 for Count = 93 to 110 ; 21 RtnChar = IsItPrime2(Count) ; 22 if (RtnChar = 'N') ; 23 dsply ('2: ' + %char(Count) + ' not prime') ; 24 elseif (RtnChar = 'Y') ; 25 dsply ('2: ' + %char(Count) + ' prime') ; 26 elseif (RtnChar = 'E') ; 27 dsply ('2: ' + %char(Count) + ' cannot be prime') ; 28 endif ; 29 endfor ; 30 *inlr = *on ; |

Line 2: These are two of my favorite control options. I always like to use the source statement number as the program sequence number. And I am giving the binding directory that my module is in.

Lines 3 – 7: Including the procedure prototypes into this program.

Lines 10 – 15: Call the first procedure to check numbers 1 – 11 for which of these numbers are primes.

Lines 20 – 22: Call the second procedure to check which numbers between 93 and 110 are primes.

Lines 11 and 21: The procedure is called passing it the number used in the FOR group. The value returned is placed in the variable `RtnChar`.

Lines 12 – 18 and 22 – 28: Display a message depending upon the value returned from the procedure.

When this program is compiled and run I see:

DSPLY 1: 1 cannot be prime DSPLY 1: 2 prime DSPLY 1: 3 prime DSPLY 1: 4 not prime DSPLY 1: 5 prime DSPLY 1: 6 not prime DSPLY 1: 7 prime DSPLY 1: 8 not prime DSPLY 1: 9 not prime DSPLY 1: 10 not prime DSPLY 1: 11 prime DSPLY 2: 93 not prime DSPLY 2: 94 not prime DSPLY 2: 95 not prime DSPLY 2: 96 not prime DSPLY 2: 97 prime DSPLY 2: 98 not prime DSPLY 2: 99 not prime DSPLY 2: 100 not prime DSPLY 2: 101 prime DSPLY 2: 102 not prime DSPLY 2: 103 prime DSPLY 2: 104 not prime DSPLY 2: 105 not prime DSPLY 2: 106 not prime DSPLY 2: 107 prime DSPLY 2: 108 not prime DSPLY 2: 109 prime DSPLY 2: 110 not prime |

This article was written for *IBM i* 7.4, and should work for some earlier releases too.

Perhaps they were looking for a simple recursive procedure as prime numbers are one of the first recursive procedures learned. Recursion is a tool that is not typically in an RPGer's toolbox, and might give the interviewer insight into the interviewee.

ReplyDeleteThis works for me:

dcl-proc isPrime;

dcl-pi *n ind;

n int(10) const; // returns if n is prime

d int(10) const; // current divisor to check

end-pi;

// base cases

if n <= 2;

return (n = 2);

endif;

if %rem(n: d) = 0;

return *off;

endif;

if d * d > n;

return *on;

endif;

return isPrime(n: d + 1);

end-proc isPrime;

// hat tip to geeksforgeeks.org/recursive-program-prime-number/

A little mistake in the program : line 50, You have the same value twice, this means that the table should only be 25 elements, which match my count of primes below 100.

ReplyDeleteI did the count using recursive sql just for the fun of it :

This sql stamtent lists alle primes from 1 to 100

WITH NUMBERS (LEVEL, PRIME) AS

( SELECT * FROM (values(1,1))

UNION ALL

SELECT LEVEL + 1, LEVEL + 1 FROM NUMBERS WHERE LEVEL < 100

)

SELECT X.PRIME FROM (SELECT NUMBERS.LEVEL, NUMBERS.PRIME FROM NUMBERS ) AS X

WHERE NOT EXISTS

(SELECT 1 FROM NUMBERS Y WHERE Y.PRIME BETWEEN 2 AND SQRT(X.PRIME) AND MOD(X.PRIME, Y.PRIME) = 0)

and X.PRIME > 1

ORDER BY X.PRIME

Best regard Jan

Thank you for reporting that mistake. I have struck it out to show that it is there in error.

DeleteYou only have to test divisors up to the square root of the number you're testing for primality, so you can bail out of the loop early if the element is > %SQRT(InNumber).

ReplyDelete