Solution 3 D

The class Primes as implemented above works just fine. However, it is an example of a situation very common in programming, i.e. there is more than one way to solve any programming problem. In spite of the fact that this class achieves exactly what was required by the problem, it is pedestrian, inflexible and inefficient.

It's perfectly true that we can find prime numbers by dividing a target integer by every integer between 1 and the target integer itself, and then checking to see if any of the smaller integers are a factor of the target integer. If we apply our mind to the problem of how we can recognise that an integer is prime however, we soon find that the above method is very inefficient.

1. To begin with, it's obvious that no even integer greater than 2 can be prime because 2 is a factor of every even integer.
2. No integer greater than half the target integer can be a factor of the target integer; if K > A/2 and K < A then A/K will result in 1.xxx; i.e. K will always divide into A once plus a remainder.
3. No odd number has an even factor.
4. Fixing the upper bound in the outer loop makes this class very inflexible; it's better to assign the upper bound to a variable and then use the variable wherever needed. This makes it easy to change the upper bound without having to search through the code for every occurrence of the upper bound in order to change it to the new value.

We can therefore make our class much more efficient and more elegant by using a variable for the upper bound, not bothering to consider any even integers in the primes search, not testing for any factors greater than half the integer, and not testing even factors. The last three things will increase the efficiency of the class enormously - the number of iterations of each loop in the class will be halved thus reducing the computation time by about 75%. Not too shabby...! You will see the immediate benefit of this if you change the upper bound in Primes from 1 thousand to 10 thousand - the class now takes an appreciable time to complete its deliberations. The image below illustrates class PrimeNums, the improvement on class Primes.

PrimeNums contains more lines of code, but the class is far more efficient.

Note also that the PrimeNums class makes use of the ability of Java to cast one data type into another in the expression:

(int)(k/2+1)

which casts the number produced by k divided by 2 into an integer (if k is an odd number k/2 will result in a double).

Note the statement

for(int k=7;k<upper;k+=2){

in PrimeNums.java - this loop increments in steps of 2 instead of the usual 1. A loop can be incremented by any integer value in this way. In the case of PrimeNums.java it allows us to skip all even numbers between 7 and the integer value upper in the process of determining prime numbers. This a considerable improvement on class Primes because it instantly halves the number of iterations of the loop that generates the integers. Classes Primes and PrimeNums achieve exactly the same end; however PrimeNums is much more efficient and contains code that is more elegant than Primes. One of your important aims as a programmer should be to write code that is as efficient and elegant as you can make it, in order to reduce the demand made on the CPU and reduce the processing time. Don't be complacent when you've found a solution to a programming problem - think about it some more in case there is a better and more elegant way to do it. A thing of beauty is a joy forever!

Download PrimeNums.java and then compile and run it. Now set the upper bound in both Primes and PrimeNums to be 10 thousand; recompile and run both to see the difference in efficiency. You can set the upper limit as high as 100 thousand, but be cautious above this if you don't want to wait for a very long time for your code to stop running...

PrimeNums still does not represent the most efficient algorithm for detecting prime numbers, but it's fine for our purposes. If you'd like to see a slight improvement on PrimeNums, download GetPrimes.java. The latter class is a little beyond your current level as Java programmers, but in Exercises 4 at the end of the next chapter there is a problem that will help you learn to deal with static values and methods.

© G. Hearn, & University of the Western Cape, 2006