Probably the least efficient way possible to determine the primality of a number is to divide it by every number up the number under examination. If any number divides in exactly, then the number is not prime. This is incredibly inefficient as it checks for factors when factors of the factors being tried have already been discarded. For example, if we have already determined that 5 is not a factor, then 10 cannot be a factor either.

As an exercise in Pascal for my degree, I was required to write a Delphi Unit for using this method to find a number's primality. One concession to efficiency was made - if a factor has not been found by the ceiling function of the square root of the test number, then it will never be found. This is because factors come in pairs and they cannot both be greater than the square root. Here is the code, for numbers greater than 1:

unit PrimalityTest; //This Unit contains a function to perform a primality test on a given integer. //It returns TRUE if the number is prime, FALSE if it is composite. interface function primality(TestNo :integer):boolean; implementation function primality(TestNo :integer):boolean; var divisor : integer; limit : integer; begin result:=TRUE; divisor:=2; limit:=trunc(Sqrt(TestNo))+1; while result AND ( divisor < limit ) do if (TestNo mod divisor) = 0 then result:=FALSE else inc(divisor); end; //primality() end.

If you are planning on using this method or code in anything at all, be aware that most of it is almost a complete waste of time (half the numbers are multiples of two, one third are multiples of three and so on). Use a better method, or hope no one ever looks at your code and links it to your processor time-wasting hide.

Thanks to StrawberryFrog, kthejoker and wntrmute for pointing out the errors in my (clearly crappy) code and mathematical reasoning. (See what happens when I don't have Google to help me?)

Log in or register to write something here or to contact authors.