# Hiking around HackerRank — 0

# 07/11/2020

Note:

- All problems are published by HackerRank, credit to HackerRank
- 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 Scannerscanner= 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 Scannerscanner= 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:

importjava.io.*;importjava.math.*;importjava.security.*;importjava.text.*;importjava.util.*;importjava.util.concurrent.*;importjava.util.regex.*;publicclassSolution {privatestaticfinalScanner scanner =newScanner(System.in);publicstaticvoidmain(String[] args) {//String n = scanner.nextLine();BigInteger num =newBigInteger(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!