Coding problem · Easy · Basics

Is It Prime?

Easy Algorithms & data structures

Return true if n is a prime number: greater than 1 and divisible only by 1 and itself.

Example 1

Input: n = 7
Output: true

Example 2

Input: n = 9
Output: false

Example 3

Input: n = 1
Output: false

Hints

Hint 1

Numbers below 2 aren't prime.

Hint 2

You only need to test divisors up to √n: if n = a × b, one of them is at most √n.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(√n) · Space O(1)

Return false for n < 2, then try divisors d while d * d <= n. Checking up to √n instead of n makes it O(√n).

Reference solution

function isPrime(n) {
  if (n < 2) return false;
  for (let d = 2; d * d <= n; d++) if (n % d === 0) return false;
  return true;
}

function isPrime(n: number): boolean {
  if (n < 2) return false;
  for (let d = 2; d * d <= n; d++) if (n % d === 0) return false;
  return true;
}

def is_prime(n: int) -> bool:
    if n < 2:
        return False
    d = 2
    while d * d <= n:
        if n % d == 0:
            return False
        d += 1
    return True

<?php

function isPrime(int $n): bool
{
    if ($n < 2) {
        return false;
    }
    for ($d = 2; $d * $d <= $n; $d++) {
        if ($n % $d === 0) {
            return false;
        }
    }
    return true;
}

class Solution {
    public boolean isPrime(int n) {
        if (n < 2) return false;
        for (int d = 2; (long) d * d <= n; d++) if (n % d == 0) return false;
        return true;
    }
}

Was this page helpful?