Check Prime Number

Introduction

Determining whether a number N is prime is a straightforward process. You can check if N is divisible by any number from 2 up to the square root of N. If N is divisible by any of these numbers, then it's not a prime number; otherwise, it is prime.

For instance, consider N=17. We iterate from 2 up to sqrt(17) i.e. 4 (inclusive), checking if any of these numbers divide N. If we find such a divisor, N is not prime; otherwise, it is prime.

This can be achieved by a simple code shown below:

Code

Java

public class Main {
    public static boolean isPrime(int n) {
        if (n == 1)
            return false; // by definition, 1 is not a prime number
        if (n == 2)
            return true; // the only even prime number
        for (int i = 2; i * i <= n; ++i) {
            if (n % i == 0)
                return false;
        }
        return true;
    }

    public static void main(String[] args) {
        int n = 17;
        if (isPrime(n))
            System.out.println("It is a Prime Number");
        else
            System.out.println("It is a Non-Prime Number");
    }
}

C++

#include <iostream>
using namespace std;

bool isPrime(int n) {
    if(n == 1)
        return false; // by definition, 1 is not prime number
    if(n == 2)
        return true; // the only one even prime
    for(int i = 2; i * i <= n; ++i) {
        if(n % i == 0)
            return false;
    }
    return true;
}

int main() {
    int n = 17;
    if(isPrime(n))
        cout << "It is a Prime Number";
    else
        cout << "It is a Non-Prime Number";
}

Python

def is_prime(n):
    if n == 1:
        return False  # by definition, 1 is not a prime number
    if n == 2:
        return True  # the only even prime number
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

if __name__ == "__main__":
    n = 17
    if is_prime(n):
        print("It is a Prime Number")
    else:
        print("It is a Non-Prime Number")

A Tiny Optimization

The above solution takes O(sqrt(n)) time. We do not need to check all even numbers, it can be optimized a bit. Have a look at the code below.

Code

Java

public class Main {
    public static boolean isPrime(int n) {
        if (n == 1)
            return false; // by definition, 1 is not a prime number
        if (n == 2)
            return true; // the only even prime number
        if(n % 2 == 0) // check if it is even
            return false;
        for(int i = 3; i * i <= n; i += 2) {
            if(n % i == 0)
                return false;
        }
            return true;
        }

    public static void main(String[] args) {
        int n = 17;
        if (isPrime(n))
            System.out.println("It is a Prime Number");
        else
            System.out.println("It is a Non-Prime Number");
    }
}

C++

#include <iostream>
using namespace std;

bool isPrime(int n) {
    if(n == 1)
        return false; // by definition, 1 is not prime number
    if(n == 2)
        return true; // the only one even prime
    if(n % 2 == 0) // check if it is even
        return false;
    for(int i = 3; i * i <= n; i += 2) {
        if(n % i == 0)
            return false;
    }
    return true;
}

int main() {
    int n = 17;
    if(isPrime(n))
        cout << "It is a Prime Number";
    else
        cout << "It is a Non-Prime Number";
}

Python

def is_prime(n):
    if n == 1:
        return False # by definition, 1 is not a prime number
    if n == 2:
        return True # the only even prime number
    if n % 2 == 0: # check if n is even
        return False
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            return False
    return True

if __name__ == "__main__":
    n = 18
    if is_prime(n):
        print("It is a Prime Number")
    else:
        print("It is a Non-Prime Number")

Conclusion

• The code is almost similar to the previous version. In addition to the first approach we checked if the n is even. Then, we return false.
• Also, we used the increment by 2 expression to skip every even number from 3 to sqrt(n).

Problem?

Let’s say that it takes 1/2 of sqrt(n) steps as we are skipping every even number. That means it takes 50,000 steps to check if 10,000,000,000 is a prime number or not. The time complexity to check prime numbers till any number n will be O(n*sqrt(n)), where n is the total number of numbers and sqrt(n) is the time to check any number if it's prime or not.

Thus, we still have a large time complexity, and the question is whether we can do better at decreasing the complexity to a linear time.