Program to Find Whether a Number is Prime

Problem: "An integer greater than 1 is said to be *prime* if it has no divisors other than itself and one. The number 17, for example, is prime because it has no factors other than 1 and 17. The number 91, however, is not prime because it is divisible by 7 and 13. Write a predicate methode isPrime(n) that returns *true* if the integer n is prime, and *false* otherwise. As an initial strategy implement isPrime using a brute-force algorithm that simply tests every possible divisor. Once you have that version working, try to come up with improvements to your algorithm that increase its efficiency without sacrificing its correctness." (Roberts ch 5, problem 11).

Code:

/*
* File: isPrimeSmarty.java
* Name: Chu
* Section Leader: 
* Description: This program lets the user enter in as many positive integers as she likes and calls the 
* private boolean "isPrimeSmarty" to evaluate whether the integer is prime or not. We also had the 
* isPrimeBrute method evaluate it, but optimized the method so that instead of testing all divisors
* you only have to iterate up to the square root of the tested number.
* 
*/

 
package ch6_practice;
import acm.program.*;

public class primeTesterSmarty extends ConsoleProgram {
   
    public void run() {
        println("This program evaluates whether positive integer is prime or not.");
        
        while (true) {        
            int number = readInt("Enter any positive integer, and enter 0 to stop:");
                if (number == 0) {
                    break;
                }
                if (number < 0) {
                    println ("Positive integer please! Why are you messin with me, thug? No more primes for you.");
                    break;
                }
                if (isPrimeSmarty(number)) {
                    println ("Yes," + number + " is a prime number.");
                }
            else println ("Nope, not a prime number.");
            }
        println("Thanks for playing.");
    }

    private boolean isPrimeSmarty(int number) {
        int k = (int)Math.sqrt(number); //Find the square root of the number you're testing for, 
        //return it rounded down to the integer
        for (int i = 2; i < k; i++){
            if (number % i == 0) {
                return false;
            }
        }
        return true;
    }
    
    // The old brute force way, commented out
    //private boolean isPrimeBrute (int number){
    //    for (int i = 2; i < number; i++){
    //        if (number % i == 0) {
    //            return false;
    //        }
    //    }
    //    return true;
    //}
}

What it looks like:

It's fun to solve problems and methodically optimize them as you think about them more, or as you learn more revisit old problems with new knowledge. This problem had a brute method solution and two potential optimizations, one that I implemented and one that I think I need to hold off on implementing until I learn more.

Brute Method: 

For any given number, iterate from 2 to that number and divide your tested number by the iterator. Is there a remainder? If you ever find a divisor where the remainder ==0, then return false, because it was divisible by a number *other than* itself and 1. If you don’t find a divisor other than itself an one, then return true.



Optimization1:

Instead of iterating from 2 to the tested number, you only need to go from 1 to the square root (rounded down to the integer) that number, so it cuts down the number of operations you have to do.

Why are we able to only test up to the square root?

Think of the tested number 21 for example.
Its divisors are: [1, 3, 7, 21].
The square root is 4.58. Under the brute force way we'd test all numbers between and including 2 and 20. Now we just test the numbers between and including 2 and 4. When we test dividing 21 by 3, the result is 7, so if we were to test out 7, we'd get the result of 3. Divisors come in pairs, and one is always less than and the other is always greater than the square root, and the square root’s value is in the middle of the list of divisors. If there was a number greater than the square root that would have shown us that the tested number is not a prime, we would have already caught it by dividing its smaller side of the pair.



Optimization2:

Once you’ve tested dividing a number by one of the iterators, you don’t need to test dividing it by a previously-tested-iterator to the n. So if you already tested 3, then you don’t need to test for 9, because if it’s divisible by 9 (aka 3 to the ^2) it’s definitely divisible by 3.

I’m not sure how to implement this second optimization. I suspect you’d have to mess with the line “for (int i = 2; i < k; i++)”, and instead of “i++” (iterating up by increments of 1) you’d want to iterate up but exclude iterators that have a previous iterator as one of its factors.

I think the way you’d do this is by creating an array that is made up of prime numbers (so that no number has any of the others as a factor) and instead of doing “i++”, you’d iterate through each value in the array. However, you don’t really know how big the array has to be, since it depends on how high the number you need to test is, so this array will probably be built on the fly as you run the program (recursive function?) I think that the syntax to implement this optimization is beyond what I know so far with Java, but I’ll come back to it later...