This lab tackles the classic and important problem of prime numbers, positive integers that are exactly divisible only by one and by themselves. Create a class Primes to contain the following three static methods to quickly produce and examine integers for their primality.

public static boolean isPrime(int n)

Checks whether the parameter integer n is a prime number. It is sufficient to use the plain old trial division algorithm for this purpose. If an integer has any nontrivial factors, at least one of these factors has to be less than or equal to its square root, so it is pointless to look for any such factors past that point, if you haven't already found any. To optimize this further, you realize that it is enough to test for divisibility of n only by primes up to the square root of n.

public static int kthPrime(int k)

Find and return the k:th element (counting from zero, as usual in computer science) from the infinite sequence of all prime numbers 2, 3, 5, 7, 11, 13, 17, 19, 23, ... This method may assume that k is nonnegative.

public static List factorize(int n)

Compute and return the list of prime factors of the positive integer n. The exact subtype of the returned List does not matter as long as the returned list contains the prime factors of n in ascending sorted order, each prime factor listed exactly as many times as it appears in the product. For example, when called with the argument n=220, this method would return some kind of List object that prints out as [2, 2, 5, 11].

To make the previous methods maximally speedy and efficient, this entire exercise is all about caching and remembering the things that you have already found out so that you don't need to waste time finding out those same things later. As the famous space-time tradeoff principle of computer science informs us, you can occasionally make your program run faster by making it use more memory. Since these days we are blessed with ample memory to splurge around with, we are usually happy to accept this tradeoff to speed up our programs.

This class should maintain a private instance of List in which you store the sequence of the prime numbers that you have already discovered, which then allows you to quickly look up and return the k:th prime number in the method kthPrime, and also to quickly iterate through the prime numbers up to the square root of n inside the method isPrime. You can use the example program primes.py from the instructor's Python version of CCPS 109 as a model of this idea. It would also be a good idea to write a private helper method expandPrimes that finds and appends new prime numbers to this list as needed by the isPrime and kthPrime methods.

To qualify for the lab marks, the automated test must successfully finish all three tests within one minute when run on the average off-the-shelf desktop computer from the past five years. Speed is the essence of this lab. Dont repeat the same computations over and over again, but cache the answers for future access into some easy and convenient data structure such as the list of all the prime numbers that you have generated so far up to some p.

-------------------------------------

referenced primes.py file:

# So that we can quickly search from the sorted __primelist. import bisect from math import sqrt # This module defines utility functions that generate prime numbers # so that these generated primes are cached for quick later access. # The list of prime numbers that we know so far. This will grow, # as these are just to "prime the pump", heh. __primelist = [2, 3, 5, 7, 11] # How far to expand the __primelist. __prime_max = 10 ** 6 # Determine whether integer n is prime, by checking its divisibility # by all known prime integers up to the square root of n. def __is_prime(n): # To check whether n is prime, check its divisibility with # all known prime numbers up to the square root of n. upper = 1 + int(sqrt(n)) # First ensure that we have enough primes to do the test. __expand_primes(upper) for d in __primelist: if n % d == 0: return False if d * d > n: return True return True # Expand the list of known primes until it the highest integer that # it contains is at least n. def __expand_primes(n): # Start looking for new primes after the largest prime we know. m = __primelist[-1] + 2 while n > __primelist[-1]: if __is_prime(m): __primelist.append(m) m += 2 # The public functions for the user code that imports this module. # Determine if the parameter integer n is a prime number. def is_prime(n): # Negative numbers, zero and one are not prime numbers. if n < 2: return False if n < __prime_max: # Expand the list of known primes until largest is >= n. __expand_primes(n) # Use binary search to determine if n is a prime. idx = bisect.bisect_left(__primelist, n) return __primelist[idx] == n else: # Determine primality of n the hard way. return __is_prime(n) # Compute the k:th prime number in the sequence of all primes. def kth_prime(k): # Expand the list of known primes until it contains at least k primes. while len(__primelist) < k + 1: __expand_primes(__primelist[-1] + 2) # Look up the k:th prime from the list of known primes. return __primelist[k] # For demonstration purposes when not imported as a module. if __name__ == "__main__": print("Here are the first 100 prime numbers.") print([kth_prime(k) for k in range(100)]) print(f"The primelist now has {len(__primelist)} elements.") for k in (999, 9999, 99999): print(f"The {k}:th prime number is {kth_prime(k)}.") print(f"The primelist now has {len(__primelist)} elements.") print("Finally, let us find some Mersenne primes of form 2**n-1.") for p in range(40): n = 2**p - 1 if is_prime(n): print(f"2**{p} - 1 = {n} is a Mersenne prime.")

ile:

J Unit Test:

import static org.junit.Assert.*; import org.junit.After; import org.junit.Before; import org.junit.Test;

import java.io.*; import java.util.*; import java.util.zip.CRC32;

public class PrimesTest { @Test public void isPrimeTest() { CRC32 check = new CRC32(); for(int k = 0; k < 10_000_000; k++) { if(Primes.isPrime(k)) { check.update(k); } } assertEquals(783904569L, check.getValue()); } @Test public void kthPrimeTest() { CRC32 check = new CRC32(); for(int k = 0; k < 30_000; k++) { check.update(Primes.kthPrime(k)); } assertEquals(3080752681L, check.getValue()); System.out.println(check.getValue()); } @Test public void factorizeTest() { CRC32 check = new CRC32(); for(int k = 2; k < 500_000; k++) { List factors = Primes.factorize(k); int prod = 1; int prev = 0; for(int f: factors) { assertTrue(f >= prev); prev = f; prod = prod * f; check.update(f); } assertEquals(k, prod); } assertEquals(2607517043L, check.getValue()); } }