Lab 11: And You Will Find Me, Prime After Prime JUnit: PrimesTest.java “There are only two hard things in Computer Scien

[answerhappygod]

Lab 11: And You Will Find Me, Prime After Prime
JUnit: PrimesTest.java
“There are only two hard things in Computer Science: cacheinvalidation and naming things.” — Phil Karlton
“All programming is anexercise in caching.” — TerjeMathisen
“Good programming turnscaching into cha-ching!” — Ilkka’scorollary
This lab tackles the classic and important problem ofprime numbers, positive integersthat are exactly divisible only by one and by themselves. Create aclass Primes to contain the following three static methods toquickly produce and examine integers for their primality.
public static boolean isPrime(int n)
Checks whether the parameter integer n is a prime number. It issufYicient to use the plain old trialdivision algorithm for this purpose. If an integerhas any nontrivial factors, at least one of these factors has to beless than or equal to its square root, so it is pointless to lookfor any such factors past that point, if you haven't already foundany. To optimize this further, you realize that it is enough totest for divisibility of n only by primes up to the square root ofn.
public static int kthPrime(int k)
Find and return the k:th element (counting from zero, as usualin computer science) from the inYinite sequence of all primenumbers 2, 3, 5, 7, 11, 13, 17, 19, 23, ... This method may assumethat k is nonnegative.
public static List<Integer> factorize(int n)
Compute and return the list of primefactors of the positive integer n. The exactsubtype of the returned List does not matter as long as thereturned list contains the prime factors of n inascending sortedorder, each prime factor listed exactly as manytimes as it appears in the product. For example, when called withthe argument n=220, this method would return some kind ofList<Integer> object that prints out as [2, 2, 5, 11].
To make the previous methods maximally speedy and efYicient,this entire exercise is all about cachingand rememberingthe things thatyou have alreadyfound out so that you don't needto waste time Yinding out those same things later. As the famousspace-time tradeoff principle of computer science informs us, youcan occasionally make your program run faster by making it use morememory. Since these days we are blessed with ample memory tosplurge around with, we are usually happy to accept this tradeoffto speed up our programs.
This class should maintain a private instance ofArrayList<Integer> in which you store the sequence of theprime numbers that you have already discovered, and lazilyexpand this list by generating and appending new primes toits end. Knowing that this list of all prime numbers up to
the current upper limit is sorted not only allows you to quicklylook up and return the k:th prime number in the method kthPrime,but also to quickly iterate through all prime numbers up to thesquare root of n inside the method isPrime to look for potentialdivisors.
Furthermore, Collections.binarySearch can be used on the sortedlist of these so far known prime numbers to determine almostinstantly whether some given positive integer is a prime number.You can use the example program primes.py from the instructor'sPython version of CCPS 109 as a model of this idea. It wouldprobably be a good idea to have a private helper methodexpandPrimes that Yinds and appends new prime numbers to this listas needed by the isPrime and kthPrime methods.
Speed is the essence of this lab. To qualify for the passing labmarks, the automated test must successfully /inishall three testswithin tenseconds on the average off-the-shelf desktopcomputer from the past Yive years. (This requirement used to betwenty seconds, but as you know, Moore's law and all that otherstuff.) At this point, you might as well also check out Lab 51,"Miller- Rabin Primality Test", for an alternative algorithm torapidly determine the primality of the given positive longinteger.
TEST CODE:
}