Hits: 43
This article concerns the matter of prime numbers in writing computer programs that generate random magic squares of order n where n is prime. My article, like all the other articles in this series, is aimed at hobbyists.
Suppose you wanted to use the Reichmann (1957) algorithm to generate prime-ordered magic squares of any size n where n ≥ 5. If you asked a user to enter a prime number for the square dimensions, there comes a point where the user won’t exactly know, and shouldn’t be expected to know, if a large number is prime. Could an average person be expected to know, off the top of their head, that 127 is prime, for example? Or what about the number 349,871? Both are prime, but I cheated: I used software. But how does the software do it, since that is what you were trying to write?
We’ll get into the algorithm details in a bit. But the easiest thing to do is to have a detection if a number is not prime. If it isn’t prime, then you can’t use Reichmann’s algorithm, and you then need to ask the user for another (hopefully prime) number that is 5 or more. The user is making at best, quasi-educated guesses. Maybe he knows some powers of 2, and by subtracting 1, he could stumble on a Mersenne prime such as the number 127 mentioned earlier, or 31. Or 7.
Prime numbers are numbers divisible by 1 and itself, and has no other factors. A number like 5 is prime because only 1 and 5 divide it evenly. The same can be said of the number 2, since 1 and 2 are its only factors, making it the only even prime number. Numbers which have more than two factors are called composite numbers. A number like 12 has 1, 2, 3, 4, 6, and 12 as factors, and thus is not prime.
Mersenne primes refer to a special class of primes. They are primes of the general formula 
, where the exponent 
is also a positive prime number.
A programmer could start with a short list of known primes in an array. Let’s say: 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, or the primes from 0 to 100. By the Fundamental Theorem of Arithmetic, a number n is composite if any prime number 
divides it. The symbols 
represent the floor function which takes the square root of 
and essentially chops off the decimal, returning only the integer part of the number. The array of known primes is thus good up to 
.
This is a shortcut, but if the user enters larger numbers than 10,000, you can try numbers beyond the scope of your array. But since the computer program doesn’t know any primes offhand beyond 97, the program could then attempt to check each whole number after 97, sqeuentially up to 
to see if anything divides n evenly. If none are found, then n is prime.
That’s a whole lot more efficient than checking each integer one by one up to n (or even 
, or half of n with the decimal chopped off) to see what divides n, if anything.
If no upper limit of n is specified to the user, even your more efficient could take hours or days to determine if n is prime, even on a computer considered to be fast. Also, for an 
magic square, it would be nice if there were only enough rows and columns to be reasonably displayed on a spreadsheet or console screen. On a spreadsheet, there is always the scrollbar to help you see the numbers that ran off the display. A 
magic square is possible for example, but requires a lot of scrolling to see the 10,201 cells containing the numbers. Today’s computers have lots of memory, so while it is possible to go far beyond even that, there is a matter of practicality. While it might be possible to check the correctness of a 
magic square programmatically, the 105.5 billion numbers it contains preclude the idea that it can be done on a normal household desktop computer running with 8 gigs of RAM.