Problem #3

Problem: Design an algorithm that prints out all the prime numbers between 1 and the given number.

Example: input -> 10
2
3
4
5
7

Algorithm: In order to solve this problem I used dynamic programming to greatly reduce the number of prime checks I had to do. I formatted the code so that the parameter would be a command line input and thus the first portion of the main function is simple exception catching and error handling. Then because you want the primes between 1 and the given number as long as the number is not negative or 1 then 2 will always be on the prime list so I add it to an ArrayList of Integers. Then I used a for loop to go through all the numbers between 3 and the given number inclusive. To check if the current number is prime I used a step wise test:

Steps:

• Check is the number is even
• If it is then it cannot be prime
• Find the square root of the number
• Check all numbers from the prime list already built and the sort
• If it is evenly divisible by an of these numbers it is not prime
• If it passed the above test then it is prime

Full Code:

import java.util.*;

public class PrimeNumGen {

/* this class takes in 2 numbers for a range, it generates and prints

all the prime numbers in the range given */

public static boolean isPrime(int i, ArrayList<Integer> list){

// this function check if a number if prime

if (i % 2 == 0 && i != 2){

// if the num is divisible by two it is not prime

// unless the num is two

return false;

}

// check all numbers between the number and its sqrt

// if the num is divisble by any of these then it is not prime

int sqrt;

if (Math.sqrt(i) % 0 != 0){

sqrt = ((int) Math.sqrt(i)) + 1;

}

else{

sqrt = (int) Math.sqrt(i);

}

int index = 1;

while (index < list.size() && list.get(index) < sqrt){

if (i % list.get(index) == 0){

return false;

}

index++;

}

return true;

}

public static void main(String[] args) {

if (args.length != 1){

// exit if the command inputs are invalid

System.err.println("Invalid Arguments.");

return;

}

int n;

try{

// try to pull the range

n = Integer.parseInt(args[0]);

  }

catch (NumberFormatException e){

// if the given arguments are not ints print an error and exit

System.err.println("Arguments must be integers.");

return;

}

// if either number is negative print an error

if (n < 0){

System.err.println("Arguments cannot be negative.");

return;

}

ArrayList<Integer> primes = new ArrayList <Integer>();

primes.add(2);

// for each number in the range check if the number is a prime

for (int i = 3; i <= n; i++){

if (isPrime(i, primes)){

primes.add(i);

}

}

for (int j = 0; j < primes.size(); j++){

System.out.println(primes.get(j));

}

}

}