The famous and significant topic of prime numbers, which are positive integers that are exactly divisible only by one and by themselves, is addressed in this lab. Create class called Primes that has the three static methods below for fast producing and examining numbers for primality.

public static boolean isPrime(int n)

The given integer n is examined to see whether it is a prime number. For this purpose, the simple old trial division algorithm is adequate. If an integer has any nontrivial factors, at least one of them must be smaller than or equal to its square root; hence, if you haven't discovered any yet, it's useless to seek for any more. To improve this even further, you notice that testing for divisibility of n solely by primes up to the square root of n suffices.

public static int kthPrime(int k)

Find and retrieve the k:th element from the infinite sequence of all prime integers 2, 3, 5, 7, 11, 13, 17, 19, 23,... It's possible that this approach assumes k isn't negative.

public static List factorize(int n)

Generate the list of prime factors of the positive integer n and return it. It makes no difference what subtype the returned List is as long as it contains the prime factors of n in ascending sorted order, with each prime factor mentioned precisely as many times as it happens in the product. When used with the input n=220, for example, this method will return a ListInteger> object with the value [2, 2, 5, 11].

This class should keep a private instance of ArrayList in which you may store the sequence of prime numbers you've previously found, and then lazy extend it by creating and attaching more primes to the end. Knowing that all prime numbers up to the current upper limit are sorted allows you to easily search up and return the k:th prime number in the method kthPrime, as well as iterate over all prime numbers up to the square root of n in the method isPrime to seek for probable divisors.

Furthermore, using the sorted list of these thus far known prime numbers, Collections.binarySearch may be used to discover whether a given positive integer is a prime number fairly rapidly. ExpandPrimes, a private helper method that discovers and appends additional prime numbers to this list as needed by the isPrime and kthPrime methods, would probably be a good idea.

To receive passing test scores, the automated test must run all three tests in under 10 seconds. To make the previous approaches as quick and effective as possible, this entire exercise is all about capturing and remembering what you've previously learned so that you don't have to waste time learning the same things again later.