FastPrim V1.3 ------------- Released September, 12th 1994 FastPrim was written 1989-1994 by Oliver Grimm. Copyright ©1994 by Oliver Grimm 1. COPYRIGHT ============ The program FastPrim and this documentation are freeware, that means you can use and spread them legally without paying any contributions (I won't reject them, too ..) as long as everything remains unmodified, and this documentation is always included in any kind of distribution. 2. DISCLAIMER ============= Of course, no warranty for anything at all ... 3. INTRODUCTION =============== FastPrim does what the name implies: it calculates prime numbers and, at least as far as I know, it calcutales them fast. It uses a method called the 'Sieve of Eratosthenes'. A description of this method can be found in section 6. The method used implies that only a finite number of primes can be calculated with a finite amount of memory, since, at least, one bit is needed for each integer in the desired interval (not for each prime number !). The interval always starts with two, so if the prime numbers up to one million should be calculated, at least one million bits (approx. 125 kByte) are necessary. However, if enough memory is avaiable (and you don't tell the program not to do so, see below) one byte instead of one bit is used, because then the calculation is faster, on a plain 68000 Amiga about twice as fast. The latter is called the 'byte model', the former the 'bit model'. 4. USAGE ======== FastPrim has to be used from the shell. No nice, cumbersome GUI ... The general command pattern of the program is the following: (Parameters in [] are optional) FastPrim [-]Number [Number] [Filename] The first number determines the upper limit of calculation and must be a positiv integer greater than one (the first prime number is, by definition, two). The optional minus sign forces the use of the bit model, even if enough memory for the byte model would be avaiable. Output of the calculated prime numbers to screen and, if desired, file will begin with the prime that is equal or greater than the second given number. If a filename is given, the primes will also be stored in a file with that name. This file is opened BEFORE the calculation starts because this avoids that you possibly realize AFTER a longer calculation that, for example, you misspelled the device name and therefore no primes can be stored. The file will contain the prime numbers as 32 bit integers, not as text, so if N prime numbers were found, the size of that file will be 4*N bytes. By the way: The 32 bits imply that the upper limit for the program is 2^32, ie. 4 billion and a bit. One rarely encounters a computer equipped with 500 megabytes of ram, but since one has virtual memory these days and big harddrives, I might include calculation routines with more bits later. If invalid parameters are given, a little help will be printed to the shell. After the program has been started, and if enough memory is avaiable, the calcualation will begin. You can abort the calculation by pressing CTRL-c. After that the prime numbers will be counted. I have seperated this from the calculation because counting itself can take a considerable amount of time. Therefore, you can now abort counting with CTRL-c without terminating the whole program, that means that the prime numbers will still be written out on screen or stored in a file after counting has been stopped with CTRL-c. If you have indicated a filename on the commandline, the primes will then be written to that file. Again, you can abort this part of the program by pressing CTRL-c. After that, the prime numbers will be given out on the screen which can be aborted by .... yes, CTRL-c. At last, the total number of primes (if you have not aborted counting) and the calculation time will be displayed. Calculation time does not include counting time, of course, and is only exact down to about one second. And ... that's it. 5. COMPATIBILITY ================ Although I have tested the program only on an Amiga 500 with OS1.3 and OS2.0, it should work on all Amiga's. If not, please drop me a note so I can fix that. 6. THE SIEVE OF ERATOSTHENES ============================ If you would like to check this 'sieve' out, here's an algorithmic description that can be followed with pen and paper. In principle, this is also what the program does. Step 1: Write down all integers from 2 up to N, where N is the number up to which you like to find all prime numbers. Step 2: Frame the '2' and then cross out every second number (that is 4,6,8,...). Step 3: If n is now the first number that is not crossed out, frame it and then cross out every n-th number. Step 4: Repeat step 3 as long as n^2 is smaller or equal than N. ---> Now all framed or not crossed out numbers are prime numbers. Simple, right ? Well, here's an example with N = 20. 1) First we write down all integers from 2 up to 20: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2) Now we 'frame' the '2' and 'cross out' every second number (I will mark them with a '^' or delete them, respectivly): 2 3 5 7 9 11 13 15 17 19 ^ 3) Now we mark the first not-crossed out number (that is the '3') and delete every third number: 2 3 5 7 11 13 17 19 ^ ^ 4) Now the next not-crossed out number is 5, but 5^2=25 and that is greater than N which is 20. So 2,3,5,7,11,13,17,19 are the prime numbers below 20. Look it up in a math book, that's correct ! Now you might also realize why the program needs at least one bit for every integer: it's used for 'marking' the numbers as crossed out or not. ---------------------- If you have any suggestions, would like to have a new function implemented, if you find any bugs or would like to send me any gifts (Well, maybe you like to write me a postcard from whereever you are), here's my address: Oliver Grimm Steinbecker Str.69 21244 Buchholz Germany E-Mail: grimm@physnet.uni-hamburg.de 'You can always make a list of what's going wrong, but your list of blessings will be twice as long.' -- Maggie Mayall