Hiking around HackerRank — 0

07/11/2020

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:

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!

Undergraduate student / Research assistant/ Always curious / Opinions are mine