# 07/11/2020

Note:

2. The solutions are coded by myself, and open source just for study.

## Java Primality Test

Interestingly, I just read this problem on ALgorithms by Robert Sedgewick and Kevin Wayne and found the solution. But in order to improve my skill, I should pretend that I haven’t read this before. (LOL)

My initial code is like this:

`import java.io.*;import java.math.*;import java.security.*;import java.text.*;import java.util.*;import java.util.concurrent.*;import java.util.regex.*;public class Solution {    static boolean primality(int n){        if (n <= 1) return false;        for (int i = 2; i < n; i ++)            if (n % i == 0)                return false;        return true;    }    private static final Scanner scanner = new Scanner(System.in);    public static void main(String[] args) {        String n = scanner.nextLine();        int num = Integer.parseInt(n);                if (! primality(num)){            System.out.println("not prime");        }        else {            System.out.println("prime");        }        scanner.close();    }}`

It worked well on 13 and 15 and passed the test, and I was confident to submit it.

However, many errors generated:

I assume it would take so much time for large numbers to finish this loop. Therefore, I must seek a more academic method, which was offered in the Algorithm:

`import java.io.*;import java.math.*;import java.security.*;import java.text.*;import java.util.*;import java.util.concurrent.*;import java.util.regex.*;public class Solution {     static boolean primality(int n){         if (n <= 1) return false;         if (n == 2 || n == 3) return true;         for (int i = 5; i * i < n; i++)             if (n % i == 0)                 return false;         return true;     }    private static final Scanner scanner = new Scanner(System.in);    public static void main(String[] args) {        //String n = scanner.nextLine();        BigInteger num = new BigInteger(scanner.next());        System.out.println(num.isProbablePrime(10)? "prime": "not prime");    }}`

Well, you know 2 and 3 are prime numbers, and square would be an efficient way to reduce the run time (maybe?). I think it would not fail this time. However, the same error generated one more time.

I was astonished and searched for the problem on the Internet. Enlightened by the HackerRank forum, I adopted the .isProbablePrime() method. The method would take certainty as a parameter and return the boolean value. You can refer to this doc on GeeksforGeeks for details. Here is my code:

Well, I would attach my a code block here, just in case:

`import java.io.*;import java.math.*;import java.security.*;import java.text.*;import java.util.*;import java.util.concurrent.*;import java.util.regex.*;public class Solution {private static final Scanner scanner = new Scanner(System.in);public static void main(String[] args) {//String n = scanner.nextLine();BigInteger num = new BigInteger(scanner.next());System.out.println(num.isProbablePrime(10)? "prime": "not prime");}}`

(The indention looks terrible. Sorry about that!)

Well, anyway, this is an interesting problem. We learned a new method and knew that loops are not omnipotent!

--

--