Hiking around HackerRank — 0

07/11/2020

Photo by Mike Kenneally on Unsplash

Note:

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

AndrewAct/HackerRank-Java-Practice

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!