Prime Check of a Big Number

Published: Sep 5, 2019

“Given an integer n, find whether n is a prime number or not” – This is a typical algorithm question. If the given number is small, repeating a division from 2 to n gives the answer.

A better solution would be to stop looping at square root of n. Suppose the given number n is not a prime number (composite number), the n has two numbers a, b where n = ab. From the equation, both a and b should be equal to or less than square root of n. So, if the factor of n exists, the factor should be the equal to or less than square root of n. Checking the number up to square root of n is enough to find n is prime or not.

However, looping over up to square root of n runs slow still once the given number becomes bigger. Well-known faster algorithm is the Sieve of Eratosthenes (Wikipedia). The algorithm starts from a boolean array of size n initialized by true value. The iteration goes from 2 to n while crossing out all multiples of 2, then 3, 5, … (set false to all multiples of 2, 3, 5…). In the end, if the last array element is true, the given number n is confirmed the prime number.

The problem of the Sieve of Eratosthenes is a memory consumption. HackerRank problem has teasing test cases of 100000003 and 1000000007. Those numbers easily cause memory out of error. The naive looping approach ends up in a timeout failure.

Combination of Sieve and Looping

There should be plenty of solutions to find a given big number is a prime or not. What came up in my mind is a combination of the sieve and looping over. The first step is to find all prime numbers up to square root of the given number using the sieve. The second step is to loop over the division by prime numbers found in the first step. This solution has the time complexity of O(square root of n), which made all HackerRank test cases pass. The solution would be a good entry here as my memo.

Latest Posts

Setting Up GCP Instance for Deep Learning

This post is going to be very different from what I write here. The content is a memo how I create a GCP (Google Cloud Platform) instance for Deep Learning. While I study algorithm stuff, I also have been studying Deep Learning. In my early days, I tried to train my Deep Learning model only on a laptop. My laptop is 2012 model MacBook Pro, so I would say it is reasonably fast. However, when it comes to Deep Learning, the training was quite painful on the such machine. Often, I ran the training over night to get a disappointed result. Still, I didn’t use any of pricey cloud environment since it was my personal study unrelated to my day job. I wanted to save money.

Complete Binary Tree

Problems which ask a binary tree traverse, add/delete nodes, etc. are popular in algorithm questions. The binary trees are often just a binary tree or binary search tree. Sometimes, the problem pinpoints a particular type of a binary tree, for example, a balanced binary tree or complete binary tree.

Catalan number

What is Catalan number ? The Catalan number belongs to the domain of combinatorial mathematics. It is a sequence of natural numbers such that: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, ... The sequence appears in counting problems. Wikipedia has the details about the sequence: Catalan Number.