music

OSdata.com

prime numbers

summary

    This subchapter looks at prime numbers.

free computer programming text book project table of contents If you like the idea of this project, then please donate some money. more information on donating

stub section

    This subchapter is a stub section. It will be filled in with instructional material later. For now it serves the purpose of a place holder for the order of instruction.

    Professors are invited to give feedback on both the proposed contents and the propsed order of this text book. Send commentary to Milo, PO Box 1361, Tustin, California, 92781, USA.

prime numbers

defined

    Prime numbers are integers greater than one that are only evenly divisible (no remainder) by one and themselves. That is, their only integer factors are one (1) and the number itself. rime numbers have no integer divsors other than one and themselves. yes, I have hinted at several alternative definitions. (NOTE: Some mathematicians include one as a prime number.)

    For example, some of the small prime numbers are 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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, and 199.

    Four is not a prime because it is divisible by two. Six is divisible by both two and three. Any even number is divisible by two. Nine is divisible by three.

    An integer greater than one is prime if its only positive divisors are itself and one.

    The reason that negative primes are excluded is because prime numbers were discovered before negative numbers and a whole lot of very interesting (and sometimes useful) patterns and properties involving prime numbers had already been discovered. Many of these patterns were not true for negative numbers. To maintain the usefulness of prime numbers, they were restricted to only pisitive numbers. Zero was discovered even later and the same principle applied for its exclusion. One is excluded because some of the useful properties don’t apply to one.

a bad example algoithm

    While looking for something completely unrelated I came across a homework answer website that gave a COBOL program that would determine if a number was a prime number or not. I won’t name the site because there is no need to embarass one particular person. I won’t go into a deep analysis of the coding mistakes because any of those could easily be fixed, even if only by trial and error.

    Of concern to us as students of software engineering is the choice of algorithm and how the algorithm might be made more efficient.

    The following is a pseudo-code version of the COBOL program. I’d reprint the original, but COBOL is very wordy and space consuming and why waste all of that space on a bad example. Further, not a whole lot of people know COBOL.

    INPUT a number (input_number);

    failure_flag := FALSE;
    DO next_possible_divisor FROM 2 UNTIL next_possible_divisor >= input_number BY STEPS of 1;
      BEGIN
        test_result := input_number MOD next_possible_divisor;
        IF (test_result == 0)
          THEN failure_flag := TRUE;
      END;
    IF (failure_flag == TRUE)
      THEN
        PRINT(input_number, ' is not a prime');
      ELSE
        PRINT(input_number, ' is a prime');
    END;

    Note that while this version initializes the flag, the original did not actually initialize its flag!

    The program uses the MOD or modular function or operation to test for whether or not a next_possible_divisor is a integral factor of the input_number. If the remainder is zero, then it is a factor and we don’t have a prime.

stopping

    If we reach the input_number, then we can stop. We didn’t need to test for greater than or equal to because we will stop at equality.

    Another obvious improvement would be to stop as soon as we have failure. Once we have determined the number isn’t a prime, we really don’t need to make any more tests. This can remove a whole bunch of tests, especially if we fail on a number such as two, three, or five.

remove even numbers

    We can also immediately remove all of the even numbers other than two from our test. This will immediately cut the number of tests almost in half.

    Becuase we know that two is the only even number that is also a prime number, we can also skip all tests of dividing (or modulo) for any number that is even. After identifying two, we never need to do any more tests with any even numbers, either as a candidate for a possible prime or as a possible divide test for a prime.

square roots

    Now, if we think about what numbers can evenly divide another number, we can cut out another large batch of tests. Numbers that aren’t prime are called composite numbers. Let’s look at a few composite numbers.

    Four is divisible by 1, 2, and 4 (1·4, 2·2, and 4·1).

    Six is divisible by 1, 2, 3, and 6 (1·6, 2·3, 3·2, and 6·1).

    Eight is divisible by 1, 2, 4, and 8 (1·8, 2·4, 4·2, and 8·1).

    Nine is divisible by 1, 3, and 9 (1·9, 3·3, 9·1).

    If you happen to notice the bold faced combinations, you might notice a special pattern about divisors.

    There are never any integer divisors that are greater than the square root of a number.

    This gives us two new tests.

    We can find the square root of our input number.

    If the square root is an integer, then we can immediately stop our test because we have already shown it isn’t a prime number.

integer floor of square root

    If the square root is a mixed number (that is, it has a fractional part), then we can use the closest integer (rounding down) as the limit for our loop. This is the integer floor function of the square root.

    Once we realize that we only need the integer floor of the square root, we can eliminate a whole bunch of square root operations. We only need to compute the square root when we skip to the next integer in the floor function sequence. And we can completely eliminate the square root computations by taking a series of squares.

    We start with 1 squared (which is one). The next in the series is two squared (which is four). We already know that both tow and three are prime numbers, but if we were to actually have a computer do the test, it can stop at one (the integer floor of both the square root of two and the square root of three).

    Our sequence of square roots that equal the integer floor of a suqare root is:

integer	1	2	3	4	5	6	7	8	9	10
square	1	4	9	16	25	36	49	64	81	100

    So, when testing the numbers from four to eight, we use the integer floor of the square root, which is two as our stopping point.

    When testing the numbers from nine to 15, we use the integer floor of the square root, which is three as our stopping point.

    When testing the numbers from 16 to 24, we use the integer floor of the square root, which is four as our stopping point.

    This pattern continues. This pattern is called perfect squares.

    Stopping at the integer floor of the square root is a much more useful optimization than removing all even numbers other than two (which saved about half our time).

    Consider the case of 101 (which is prime). The square root is a little more than 10 (the square root of 100 is 10). We can stop testing at 10. 11 times 9 is simply the reverse of the test 9 times 11, which we would have already done. This elminates about 90% of the possible tests. The efficiency (as a percentage) goes up as we test larger and larger numbers.

    Consider the case of eight. Once we determineed that eight was divisible by two, we didn’t need to check for any other multiple of two. We didn’t actually have to check to see if it was divisible by four. This was the basis of our earlier optimization of throwing out all even numbers other than two.

generating the perfect squares

    We can generate the sequence of integer floors of square roots by taking each integer in turn and multiplying iby itself.

    Another optimizationis to use simple additions.

    The sequence of perfect squares is generated by adding the consecutive odd integers.

    The first odd integer is one and its perfect square is one.

    The first two odd integers are one and three, which have a sum of four, the perfect square of two.

    The first three odd integers are one, three, and five, which have a sum of nine, the perfect square of three.

    The first four odd integers are one, three, five, and seven, which have a sum of 16, which is the perfect square of four.

    This pattern continues forever. The sum of the first n positive integers is n².

    If we keep track of where we are in the sequence, we can simply determine the next odd integer and add it to our running total and use that information for determining our stopping point.

skip composite numbers

    What other optimizations can we do?

    If we happen to be looking for a list of prime numbers rather than simply testing one arbitrary number, we can save a list of all the prime numbers we’ve already found.

    Why did we skip all even numbers other than two? Because if a number is divisible by any multiple of two (4, 6, 8, 10, …), then it is also divisible by two. No need to perform those tests.

    This principle applies to any other prime number.

    Consider 81. We don’t need to test to see that 81 is divisible by nine (nine times nine equals 81) because three is a factor of nine and by the time we reached nine we would have already determined that 81 was also divisible by three.

    We can leave all composite numbers out of our test for prime numbers. Of course, this means we need to know whether or not the next possible divisor is a prime or composite number. Hence, the optimization of keeping a list of prime numbers. As we determine each prime number, we can run our test for the next larger prime number using only the prime numbers we’ve already discovered.

better algorithms

    Are there more optimizations? Yes!

    The important principle (once again) is that we can dramatically improve the efficiency of our programs by looking at the fundamental algorithm we are using.

    Many beginning programmers point out that some of the steps that make a program clear and easy to read have a small built-in inefficiency. Cleaning up those small inefficiencies makes only a very small improvement in the total efficiency of the program (except for a few bottleneck cases). This small improvement in efficiency is not worth the headaches that occur when someone else has to come along and change your program.

    With the increasing speed and power of processors (Moore’s Law) the time saved from little tricks is trivial to the point of being insignificant.

    The real improvements in efficiency come from finding better methods (better algorithms).

    Please keep your programs readable, because the small amount of processing time you save is trivial compared to the large amount of extra time when the next programmer has to make an inevitable change. Successful programs have lasted for decades. That’s why there are still early COBOL and FORTRAN programs in use.

    For a very interesting web site about prime numbers see primes.utm.edu.

free music player coding example

    Coding example: I am making heavily documented and explained open source code for a method to play music for free — almost any song, no subscription fees, no download costs, no advertisements, all completely legal. This is done by building a front-end to YouTube (which checks the copyright permissions for you).

    View music player in action: www.musicinpublic.com/.

    Create your own copy from the original source code/ (presented for learning programming).

    Work on this project is very slow because I am homeless. I am available for work if someone can provide an indoor place to work in Costa Mesa, California, electricity, internet connections, a flat raised working surface (such as a table or desk), a sitting device (such as a chair or stool), and a fully functional reasonably modern used computer. I’m already homeless, so you don’t need to pay me (and I understand how much business people hate the minimum wage law). Just give me a chance to build work that can earn the Nobel Prize. Please. You will get more than a million dollars if I win the Nobel Prize for you. That’s more than enough to pay back the cost of rent and a computer.