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...

Fib Sequence with Method

Problem: "The Fibonacci sequence, in which each new term is the sum of the preceding two, was introduced in Ch4, exercise 9. Rewrite the program requested in that exercise, changing the implementation so that your program calls a method "fibonacci(n) to calculate the nth Fibonacci number. In terms of the number of mathematical calculations required, is your new implementation more or less efficient than the one you used in Ch 4?" (Roberts Ch 5, problem 2).

What it looks like when you run:

Here is the code:

/*

/*
* File: FibSequenceMethods.java
* Name: Renee
* Section Leader: 
* -----------------
* The Fibonacci sequence is defined as a sequence of numbers where each integer is the sum of *the two previous integers in the sequence.
* 
* This program prompts the user for an integer N and calls the private, recursive method fib(n) 
* to print out the first "n" digits of the Fibonacci Sequence. 
*/

package ch6_practice;
import acm.program.*;

public class FibSequenceMethods extends ConsoleProgram {
    public void run() {
    println("This program prints the first 'n' digits of the Fibbonacci Sequence.");
         int n = readInt("How many digits do you want to print?");         
         for (int i = 0; i < n; i++) {
          println("Fib of " + i + " is " + fib(i) + ".");
         }
         

 }
    
    private int fib(int n) {
     if (n < 2) {
         return n;
     }
         return fib(n - 1) + fib(n - 2);
     }
     
    }

Here is the old version (not using a private method):

/*
public class FibSequence extends ConsoleProgram {
    public void run() {
        //Getting the first two in the sequence started...
        int n0 = 0;
        int n1 = 1;
        println(n0);
        println(n1);

        //Now kicking off the fun part by changing moving down the variable values; n1 becomes
//n0, n2 becomes n1, and a new n2 value is created.

        for (int i = 2; i < END; i++) {
            int n2 = n1 + n0;
            println(n2);
            n0=n1;
            n1=n2;
        }
    }

    //Private constant; "End" is the the nth number in the Fib sequence displayed.
    private static final double END = 15;
}

In the new version of the program, because the part that actually calculates each entry in the sequence is a separate method call, you can use a recursive method. In other words, when you're trying to find fib(6), you have at your disposal the ability to calculate fib(5) and fib(4) whereas you didn't before. The new version of the program is easier to write because the code looks like the way we coloquially define the fib sequence. However, it is not actually more efficient (there aren't fewer operations) than the old version because to arrive at any integer in the sequence, you have to calculate *all* the previous integers before it. I drew out the operations to calculate fib(6) using both programs, below. New Version:

Old Version: