Skip to main content

Math Basics

Check if a number is prime without using the Sieve of Eratosthenes Solution In C++/Java/Python/JS

What exactly is a prime number?

A prime number is a number that is greater than 1 and has only two factors: 1 and itself. In other words, a prime number is not divisible by any other numbers except 1 and itself.

For example:

  • 7 is a prime number because it is only divisible by 1 and 7.
  • 10 is not a prime number because it is divisible by 1, 2, 5, and 10.

That makes sense! Now, let’s discuss different ways to check whether a number is prime.

Naive Approach

What is the most basic way to check for a prime number?

The simplest way is to check divisibility for every number from 2 to n-1. If the given number is divisible by any of these numbers, then it is not prime.

That sounds straightforward. Let’s go through an example.

Let's check whether n = 17 is prime.

  1. Start checking divisibility from 2 to 16.
  2. 17 is not divisible by any number from 2 to 16.
  3. Since no divisors were found, 17 is prime.

Check if a number is prime without using the Sieve of Eratosthenes Solution (Naive Approach)

Now lets checkout the "Check if a number is prime without using the Sieve of Eratosthenes" code in C++ , Java, Python and JavaScript.

"Check if a number is prime without using the Sieve of Eratosthenes" Code in all Languages.
1. Check if a number is prime without using the Sieve of Eratosthenes solution in C++ Try on Compiler 
bool isPrime(int n) {

    // Prime numbers are greater than 1.
    if (n <= 1)
        return false; 

    // Looping from 2 to n-1 to check if the number has any divisors.
    for (int i = 2; i < n; i++) {

        // If n is divisible by any number other than 1 and itself, it's not prime.
        if (n % i == 0)
            return false; 
    }

    // If no divisors are found, the number is prime.
    return true; 
}

2. Check if a number is prime without using the Sieve of Eratosthenes Solution in Java Try on Compiler 
public static boolean isPrime(int n) {
        // Prime numbers are greater than 1.
        if (n <= 1)
            return false;

        // Looping from 2 to n-1 to check for divisibility.
        for (int i = 2; i < n; i++) {
            if (n % i == 0)
                return false;
        }

        // If no divisors are found, it's prime.
        return true;
    }

3. Check if a number is prime without using the Sieve of Eratosthenes Solution in Python Try on Compiler 
def is_prime(n):
    # Prime numbers are greater than 1.
    if n <= 1:
        return False

    # Looping from 2 to n-1 to check for divisibility.
    for i in range(2, n):
        if n % i == 0:
            return False

    # If no divisors are found, it's prime.
    return True

4. Check if a number is prime without using the Sieve of Eratosthenes solution in JavaScript Try on Compiler 
function isPrime(n) {
    // Prime numbers are greater than 1
    if (n <= 1) return false;

    // Looping from 2 to n-1 to check for divisibility
    for (let i = 2; i < n; i++) {
        if (n % i === 0) return false;
    }

    // If no divisors are found, it's prime
    return true;
}

Check if a number is prime without using the Sieve of Eratosthenes Complexity Analysis

Time Complexity: O(n)

Since we are checking all numbers from 2 to n-1, the time complexity is O(n).

Space Complexity: O(1)

Since we use few variables, the space complexity is O(1).

If we observe the basic approach, we are checking divisibility for every number up to n−1. This takes too long for large n. Can we optimize it to be faster? Is there a better way to check for primality? Let's find out!

Optimized Trial Division (√n Approach)

There’s an optimization that reduces the number of checks. Instead of checking divisibility up to n-1, we can stop at √n (square root of n).

Why?
Every divisor comes in a pair. If d is a divisor of n, then n/d is also a divisor.

  • If d ≤ √n, then n/d ≥ √n
  • So, if a number has a divisor greater than its square root, its pair must be smaller than the square root, which we would have already checked!

Let’s go through an example.

Let's check n = 37 using this method.

  1. Compute √37 ≈ 6.08 → Check divisibility up to 6.
  2. Check divisibility by 2, 3, 4, 5, and 6.
  3. Since 37 is not divisible by any of these numbers, 37 is prime.

Let's first see the Optimized Trial Division (√n Approach) Algorithm to Check if a number is prime without using the Sieve of Eratosthenes.

Check if a number is prime without using the Sieve of Eratosthenes Algorithm (√n Approach)

Handle edge cases: If n ≤ 1, return false (since prime numbers are greater than 1).

Check divisibility from 2 to sqrt{n}:

    • Iterate from i=2 to sqrt{n}.
    • If n is divisible by any i, return false (since it has a factor other than 1 and itself).

If no divisors are found, return true: This means n is prime.

Now, let's see how we can code this up

Check if a number is prime without using the Sieve of Eratosthenes Solution (√n Approach)

Let's see the Optimized Trial Division (√n Approach) code in C++, Java, Python and JavaScript.

"Check if a number is prime without using the Sieve of Eratosthenes" Code in all Languages.
1. Check if a number is prime without using the Sieve of Eratosthenes solution in C++ Try on Compiler 
bool isPrime(int n) {
    if (n <= 1)
        return false;

    // Check divisibility from 2 to sqrt(n)
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0)
            return false;

    return true;
}

2. Check if a number is prime without using the Sieve of Eratosthenes Solution in Java Try on Compiler 
// Function to check if a number is prime
  static boolean isPrime(int n) {

      // Numbers ≤ 1 are not prime
      if (n <= 1)
          return false;

      // Check divisibility from 2 to sqrt(n)
      for (int i = 2; i <= Math.sqrt(n); i++) {

          // If divisible, not prime
          if (n % i == 0)
              return false;
      }

      // If no divisors are found, it's prime
      return true;
  }

3. Check if a number is prime without using the Sieve of Eratosthenes Solution in Python Try on Compiler 
# Function to check if a number is prime
def is_prime(n):

    # Numbers ≤ 1 are not prime
    if n <= 1:
        return False

    # Check divisibility from 2 to sqrt(n)
    for i in range(2, int(math.sqrt(n)) + 1):

        # If divisible, not prime
        if n % i == 0:
            return False

    # If no divisors are found, it's prime
    return True

4. Check if a number is prime without using the Sieve of Eratosthenes solution in JavaScript Try on Compiler 
// Function to check if a number is prime
function isPrime(n) {
    
    // Numbers ≤ 1 are not prime
    if (n <= 1)
        return false;

    // Check divisibility from 2 to sqrt(n)
    for (let i = 2; i <= Math.sqrt(n); i++) {
        // If divisible, not prime
        if (n % i === 0)
            return false;
    }

    // If no divisors are found, it's prime
    return true;
}

Check if a number is prime without using the Sieve of Eratosthenes Complexity Analysis

Time Complexity: O(sqrt{n})

  • The loop runs from 2 to sqrt{n}, meaning it performs approximately O(sqrt{n}) iterations.
  • Inside the loop, each iteration performs a modulus operation, which is O(1).
  • Therefore, the overall time complexity is O(sqrt{n}).

Best case: O(1)

  • If n≤1, we return immediately.
  • If n=2 or n = 3, we only check a couple of conditions.

Worst case: O(sqrt{n})

  • When n is a large prime, we check all numbers up to sqrt{n}.

Space Complexity: O(1)

  • The algorithm uses only a few integer variables (n, i) and does not use any extra data structures.
  • The space complexity is O(1) (constant space) since it does not grow with input size.
This was definitely an improvement over our initial approach, reducing the number of checks significantly! But can we optimize it even further? Let’s refine it and minimize unnecessary computations!

Optimized Trial Division (Checking Only 6k ± 1 Numbers)

Can this be improved further?

Yes! The number of checks can be reduced even more.

How?

Any integer n can be written in the form 6k + i, where i can be 0, 1, 2, 3, 4, or 5.

  • If i = 0, 2, 3, or 4, the number is divisible by 2 or 3 and cannot be prime.
  • This means prime numbers greater than 3 must be of the form 6k ± 1.

So, instead of checking all numbers up to √n, only numbers of the form 6k ± 1 need to be checked.

Let’s go through an example.

Let’s check n = 61.

  1. Check divisibility by 2 and 3 → 61 is not divisible.
  2. Compute √61 ≈ 7.81, so check up to 7.
  3. Check divisibility by 5 and 7 (since they are 6k ± 1 numbers).
  4. 61 is not divisible, so it is prime!

Check if a number is prime without using the Sieve of Eratosthenes (Checking Only 6k ± 1 Numbers Approach)

Let's see the Trial Division (Checking Only 6k ± 1 Numbers) code in C++, Java, Python and JavaScript.

"Check if a number is prime without using the Sieve of Eratosthenes" Code in all Languages.
1. Check if a number is prime without using the Sieve of Eratosthenes solution in C++ Try on Compiler 
// Function to check if a number is prime
bool isPrime(int n) {
    // Check if n is 1 or 0
    if (n <= 1)
        return false;

    // Check if n is 2 or 3
    if (n == 2 || n == 3)
        return true;

    // Check whether n is divisible by 2 or 3
    if (n % 2 == 0 || n % 3 == 0)
        return false;

    // Check from 5 to square root of n
    // Iterate i by (i+6)
    for (int i = 5; i <= sqrt(n); i += 6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }

    return true;
}

2. Check if a number is prime without using the Sieve of Eratosthenes Solution in Java Try on Compiler 
// Function to check if a number is prime
    static boolean isPrime(int n) {
        // Check if n is 1 or 0
        if (n <= 1)
            return false;

        // Check if n is 2 or 3
        if (n == 2 || n == 3)
            return true;

        // Check whether n is divisible by 2 or 3
        if (n % 2 == 0 || n % 3 == 0)
            return false;

        // Check from 5 to square root of n
        // Iterate i by (i+6)
        for (int i = 5; i <= Math.sqrt(n); i += 6) {
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
        }

        return true;
    }

3. Check if a number is prime without using the Sieve of Eratosthenes Solution in Python Try on Compiler 
# Function to check if a number is prime
def is_prime(n):
    # Check if n is 1 or 0
    if n <= 1:
        return False

    # Check if n is 2 or 3
    if n == 2 or n == 3:
        return True

    # Check whether n is divisible by 2 or 3
    if n % 2 == 0 or n % 3 == 0:
        return False

    # Check from 5 to square root of n
    # Iterate i by (i+6)
    for i in range(5, int(math.sqrt(n)) + 1, 6):
        if n % i == 0 or n % (i + 2) == 0:
            return False

    return True

4. Check if a number is prime without using the Sieve of Eratosthenes solution in JavaScript Try on Compiler 
// Function to check if a number is prime
function isPrime(n) {
    // Check if n is 1 or 0
    if (n <= 1)
        return false;

    // Check if n is 2 or 3
    if (n === 2 || n === 3)
        return true;

    // Check whether n is divisible by 2 or 3
    if (n % 2 === 0 || n % 3 === 0)
        return false;

    // Check from 5 to square root of n
    // Iterate i by (i+6)
    for (let i = 5; i <= Math.sqrt(n); i += 6) {
        if (n % i === 0 || n % (i + 2) === 0)
            return false;
    }

    return true;
}

Check if a number is prime without using the Sieve of Eratosthenes Complexity Analysis

Time Complexity: O(sqrt{n})

  • The algorithm skips even numbers and multiples of 3 after handling them separately.
  • Instead of checking all numbers up to n\sqrt{n}, it checks only numbers of the form 6k±1 (i.e., 5, 7, 11, 13, etc.).
  • This effectively reduces the number of iterations by a factor of 3, making it approximately:

O(sqrt{n} / 3) = O(sqrt{n})

👉 Best case: O(1)

  • If n≤3, the function returns immediately.

👉 Worst case: O(sqrt{n})

  • When n is a large prime, we still check up to sqrt{n}, but with fewer numbers compared to the simple trial division method.

Space Complexity: O(1)

  • The algorithm only uses a few integer variables (n, i), and no extra space is required.
  • Therefore, the space complexity is O(1) (constant space).
Determining the primality of a small number is straightforward by testing divisibility up to its square root. However, as learners of LearnYard, we must explore more efficient techniques, especially for massive numbers, where traditional methods fail. Advanced primality tests empower us to tackle such challenges in competitive environments.

Fermat’s Primality Test (Based on Modular Arithmetic)

Intuition

Fermat’s test is based on Fermat’s Little Theorem, which states that if p is a prime number and a is any integer such that 1 < a < p, then:

a^(p−1) ≡ 1 (mod p)

This means that when a is raised to the power of p - 1 and divided by p, the remainder should be 1.

Step-by-Step Example:

Let’s check if 41 is prime using Fermat’s test:

  1. Pick a random base, say a = 2.
  2. Compute 2⁴⁰ mod 41. If the result is 1, then 41 might be prime.
  3. If we get any number other than 1, 41 is definitely composite.

Check if a number is prime without using the Sieve of Eratosthenes Algorithm (Fermat’s Primality Test)

Handle base cases:

  • If n ≤ 1 or n = 4, return false (not prime).
  • If n ≤ 3, return true (prime).

Repeat the following steps kk times for better accuracy:

  1. Pick a random integer a in the range [2, n − 2].
  2. Compute: a^(n−1) mod n, using Modular Exponentiation.
  3. If the result is not 1, return false (composite).
  4. If all iterations pass, return true (probably prime).

Check if a number is prime without using the Sieve of Eratosthenes Solution (Fermat’s Primality Test)

 Let's see the Fermat’s Primality Test code in C++, Java, Python and JavaScript.

"Check if a number is prime without using the Sieve of Eratosthenes" Code in all Languages.
1. Check if a number is prime without using the Sieve of Eratosthenes solution in C++ Try on Compiler 
// Iterative Function to calculate (a^n) % p in O(log n)
int power(int a, int n, int p) {
    // Initialize result
    int res = 1;

    // Update 'a' if 'a' >= p
    a = a % p;

    while (n > 0) {
        // If n is odd, multiply 'a' with result
        if (n & 1)
            res = (res * a) % p;

        // n must be even now
        n = n >> 1; // n = n / 2
        a = (a * a) % p;
    }

    return res;
}

// If n is prime, then always returns true
// If n is composite, then returns false with high probability
// Higher value of k increases probability of correct result.
bool isPrime(int n, int k) {
    // Corner cases
    if (n <= 1 || n == 4)
        return false;

    if (n <= 3)
        return true;

    // Try k times
    while (k > 0) {
        // Pick a random number in [2..n-2]
        // Above corner cases make sure that n > 4
        int a = 2 + rand() % (n - 4);

        // Fermat's little theorem
        if (power(a, n - 1, n) != 1)
            return false;

        k--;
    }

    return true;
}

2. Check if a number is prime without using the Sieve of Eratosthenes Solution in Java Try on Compiler 
// Iterative Function to calculate (a^n) % p in O(log n)
    static int power(int a, int n, int p) {
        // Initialize result
        int res = 1;

        // Update 'a' if 'a' >= p
        a = a % p;

        while (n > 0) {
            // If n is odd, multiply 'a' with result
            if ((n & 1) == 1)
                res = (res * a) % p;

            // n must be even now
            n = n >> 1; // n = n / 2
            a = (a * a) % p;
        }

        return res;
    }

    // If n is prime, then always returns true
    // If n is composite, then returns false with high probability
    // Higher value of k increases probability of correct result.
    static boolean isPrime(int n, int k) {
        // Corner cases
        if (n <= 1 || n == 4)
            return false;

        if (n <= 3)
            return true;

        // Try k times
        while (k > 0) {

            // Pick a random number in [2..n-2]
            // Above corner cases make sure that n > 4
            int a = 2 + (int) (Math.random() * (n - 4));

            // Fermat's little theorem
            if (power(a, n - 1, n) != 1)
                return false;

            k--;
        }

        return true;
    }

3. Check if a number is prime without using the Sieve of Eratosthenes Solution in Python Try on Compiler 
# Iterative Function to calculate (a^n) % p in O(log n)
def power(a, n, p):
    # Initialize result
    res = 1

    # Update 'a' if 'a' >= p
    a = a % p

    while n > 0:
        # If n is odd, multiply 'a' with result
        if n & 1:
            res = (res * a) % p

        # n must be even now
        n = n >> 1  # n = n / 2
        a = (a * a) % p

    return res

# If n is prime, then always returns true
# If n is composite, then returns false with high probability
# Higher value of k increases probability of correct result.
def is_prime(n, k):
    # Corner cases
    if n <= 1 or n == 4:
        return False

    if n <= 3:
        return True

    # Try k times
    while k > 0:
        # Pick a random number in [2..n-2]
        # Above corner cases make sure that n > 4
        a = random.randint(2, n - 2)

        # Fermat's little theorem
        if power(a, n - 1, n) != 1:
            return False

        k -= 1

    return True

4. Check if a number is prime without using the Sieve of Eratosthenes solution in JavaScript Try on Compiler 
// Iterative Function to calculate (a^n) % p in O(log n)
function power(a, n, p) {
  
    // Initialize result
    let res = 1;

    // Update 'a' if 'a' >= p
    a = a % p;

    while (n > 0) {
      
        // If n is odd, multiply 'a' with result
        if (n & 1)
            res = (res * a) % p;

        // n must be even now
        // n = n / 2
        n = n >> 1; 
        a = (a * a) % p;
    }

    return res;
}

// If n is prime, then always returns true
// If n is composite, then returns false with high probability
// Higher value of k increases probability of correct result.
function isPrime(n, k) {
  
    // Corner cases
    if (n <= 1 || n === 4)
        return false;

    if (n <= 3)
        return true;

    // Try k times
    while (k > 0) {
        // Pick a random number in [2..n-2]
        // Above corner cases make sure that n > 4
        let a = 2 + Math.floor(Math.random() * (n - 4));

        // Fermat's little theorem
        if (power(a, n - 1, n) !== 1)
            return false;

        k--;
    }

    return true;
}

Check if a number is prime without using the Sieve of Eratosthenes Complexity Analysis

Time Complexity: O(k * logn)

Iteration Pattern

  • The test repeats k times for accuracy.
  • Each iteration picks a random number a and performs modular exponentiation.
  • Modular exponentiation is done using Exponentiation by Squaring, which runs in O(log n) time.

Recurrence Relation

Let T(n) represent the time required for the test:

  • Each iteration calls the power function, which takes O(log n) time.
  • Since the test runs k times, the total complexity follows:

T(n) = k ⋅ O(log n)

Final Time Complexity: O(k log n)

Space Complexity: O(1)

We use few variables which accumulates to a constant space, hence the total space complexity is O(1).

Some composite numbers can still pass this test, making it unreliable on its own. That's why we need a better method to ensure accurate primality testing.

Miller-Rabin Test (A Stronger Version of Fermat’s Test)

Miller-Rabin improves on Fermat’s test by preventing false positives through additional conditions.
Instead of just checking a^(p-1) ≡ 1 mod p, we express n - 1 as a power of 2 times another number:

n - 1 = 2^s × d

Then, we test whether:

  1. a^d mod n = 1
  2. Squaring repeatedly eventually gives -1 mod n

If neither happens, n is composite.

Step-by-Step Example:

Let’s check if 61 is prime:

  • Write 60 = 2² × 15 (so s = 2, d = 15).
  • Pick a random base, say a = 2.
  • Compute 2¹⁵ mod 61.
  • If it’s 1, then 61 might be prime. Otherwise, square the result and check for -1.
  • If neither condition is met, 61 is composite.

Check if a number is prime without using the Sieve of Eratosthenes Algorithm (Miller-Rabin Test)

Handle Base Cases

  • If n ≤ 1 or n = 4, return false (not prime).
  • If n ≤ 3, return true (prime).

Express (n - 1) in the Form of Power of 2

  • Find an odd number d such that n - 1 = 2^s × d for some s ≥ 1.
  • This ensures that d is the largest odd factor of n - 1.

Perform k Rounds of Testing for Accuracy

Repeat the following steps k times for better accuracy:

  1. Pick a random integer a in the range [2, n - 2].
  2. Compute x = a^d mod n using Modular Exponentiation.
  3. If x = 1 or x = n - 1, continue to the next iteration (probable prime).
  4. Otherwise, repeatedly square x and check:
    • If x = 1 at any step, return false (composite).
    • If x = n - 1 at any step, continue to the next iteration.
    • Stop squaring if d reaches n - 1.
  5. If none of the conditions hold, return false (composite).

If All Rounds Pass, Return Probable Prime: If all k iterations pass, return true (probably prime).

Check if a number is prime without using the Sieve of Eratosthenes Solution (Miller-Rabin Test)

 Let's see the Miller-Rabin Test code in C++, Java, Python and JavaScript.

"Check if a number is prime without using the Sieve of Eratosthenes" Code in all Languages.
1. Check if a number is prime without using the Sieve of Eratosthenes solution in C++ Try on Compiler 
// Utility function to do modular exponentiation.
// It returns (x^y) % p
int power(int x, int y, int p) {

    // Initialize result
    int res = 1;

    // Update x if it is more than or equal to p
    x = x % p;

    while (y > 0) {

        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x) % p;

        // y must be even now
        y = y >> 1; // y = y / 2
        x = (x * x) % p;
    }

    return res;
}

// This function is called for all k trials.
// It returns false if n is composite and
// returns true if n is probably prime.
// d is an odd number such that d * 2^r = n - 1 for some r >= 1

bool miillerTest(int d, int n) {

    // Pick a random number in [2..n-2]
    // Corner cases make sure that n > 4
    int a = 2 + rand() % (n - 4);

    // Compute a^d % n
    int x = power(a, d, n);

    if (x == 1 || x == n - 1)
        return true;

    // Keep squaring x while one of the
    // following doesn't happen
    // (i) d does not reach n-1
    // (ii) (x^2) % n is not 1
    // (iii) (x^2) % n is not n-1

    while (d != n - 1) {
        x = (x * x) % n;
        d *= 2;

        if (x == 1)
            return false;
        if (x == n - 1)
            return true;
    }

    // Return composite
    return false;
}

// It returns false if n is composite
// and returns true if n is probably prime.
// k is an input parameter that determines accuracy level.
// Higher value of k indicates more accuracy.

bool isPrime(int n, int k) {
    
    // Corner cases
    if (n <= 1 || n == 4)
        return false;
    if (n <= 3)
        return true;

    // Find d such that n = 2^d * r + 1
    // for some r >= 1
    int d = n - 1;

    while (d % 2 == 0)
        d /= 2;

    // Iterate given number of 'k' times
    for (int i = 0; i < k; i++)
        if (!miillerTest(d, n))
            return false;

    return true;
}

2. Check if a number is prime without using the Sieve of Eratosthenes Solution in Java Try on Compiler 
// Utility function to do modular exponentiation.
// It returns (x^y) % p
static int power(int x, int y, int p) {

    // Initialize result
    int res = 1;

    // Update x if it is more than or equal to p
    x = x % p;

    while (y > 0) {

        // If y is odd, multiply x with result
        if ((y & 1) == 1)
            res = (res * x) % p;

        // y must be even now
        y = y >> 1; // y = y / 2
        x = (x * x) % p;
    }

    return res;
}

// This function is called for all k trials.
// It returns false if n is composite and
// returns true if n is probably prime.
// d is an odd number such that d * 2^r = n - 1 for some r >= 1

static boolean miillerTest(int d, int n) {

    // Pick a random number in [2..n-2]
    // Corner cases make sure that n > 4
    int a = 2 + (int) (Math.random() * (n - 4));

    // Compute a^d % n
    int x = power(a, d, n);

    if (x == 1 || x == n - 1)
        return true;

    // Keep squaring x while one of the
    // following doesn't happen
    // (i) d does not reach n-1
    // (ii) (x^2) % n is not 1
    // (iii) (x^2) % n is not n-1

    while (d != n - 1) {
        x = (x * x) % n;
        d *= 2;

        if (x == 1)
            return false;
        if (x == n - 1)
            return true;
    }

    // Return composite
    return false;
}

// It returns false if n is composite
// and returns true if n is probably prime.
// k is an input parameter that determines accuracy level.
// Higher value of k indicates more accuracy.

static boolean isPrime(int n, int k) {
    
    // Corner cases
    if (n <= 1 || n == 4)
        return false;
    if (n <= 3)
        return true;

    // Find d such that n = 2^d * r + 1
    // for some r >= 1
    int d = n - 1;

    while (d % 2 == 0)
        d /= 2;

    // Iterate given number of 'k' times
    for (int i = 0; i < k; i++)
        if (!miillerTest(d, n))
            return false;

    return true;
}

3. Check if a number is prime without using the Sieve of Eratosthenes Solution in Python Try on Compiler 
# Utility function to do modular exponentiation.
# It returns (x^y) % p
def power(x, y, p):

    # Initialize result
    res = 1

    # Update x if it is more than or equal to p
    x = x % p

    while y > 0:
        # If y is odd, multiply x with result
        if y & 1:
            res = (res * x) % p

        # y must be even now
        y = y >> 1  # y = y / 2
        x = (x * x) % p

    return res

# This function is called for all k trials.
# It returns false if n is composite and
# returns true if n is probably prime.
def miiller_test(d, n):

    # Pick a random number in [2..n-2]
    a = random.randint(2, n - 2)

    # Compute a^d % n
    x = power(a, d, n)

    if x == 1 or x == n - 1:
        return True

    while d != n - 1:
        x = (x * x) % n
        d *= 2

        if x == 1:
            return False
        if x == n - 1:
            return True

    return False

# It returns false if n is composite
# and returns true if n is probably prime.
def is_prime(n, k):
    if n <= 1 or n == 4:
        return False
    if n <= 3:
        return True

    d = n - 1
    while d % 2 == 0:
        d //= 2

    for _ in range(k):
        if not miiller_test(d, n):
            return False

    return True

4. Check if a number is prime without using the Sieve of Eratosthenes solution in JavaScript Try on Compiler 
// Utility function to do modular exponentiation.
// It returns (x^y) % p
function power(x, y, p) {
  
    // Initialize result
    let res = 1;

    // Update x if it is more than or equal to p
    x = x % p;

    while (y > 0) {
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x) % p;

        // y must be even now
        y = y >> 1; // y = y / 2
        x = (x * x) % p;
    }

    return res;
}

// This function is called for all k trials.
// It returns false if n is composite and
// returns true if n is probably prime.
// d is an odd number such that d * 2^r = n - 1 for some r >= 1

function miillerTest(d, n) {
    // Pick a random number in [2..n-2]
    // Corner cases make sure that n > 4
    let a = 2 + Math.floor(Math.random() * (n - 4));

    // Compute a^d % n
    let x = power(a, d, n);

    if (x === 1 || x === n - 1)
        return true;

    // Keep squaring x while one of the
    // following doesn't happen
    // (i) d does not reach n-1
    // (ii) (x^2) % n is not 1
    // (iii) (x^2) % n is not n-1
  
    while (d !== n - 1) {
        x = (x * x) % n;
        d *= 2;

        if (x === 1)
            return false;
        if (x === n - 1)
            return true;
    }

    // Return composite
    return false;
}

// It returns false if n is composite
// and returns true if n is probably prime.
// k is an input parameter that determines accuracy level.
// Higher value of k indicates more accuracy.

function isPrime(n, k) {
    // Corner cases
    if (n <= 1 || n === 4)
        return false;
    if (n <= 3)
        return true;

    // Find d such that n = 2^d * r + 1
    // for some r >= 1
    let d = n - 1;

    while (d % 2 === 0)
        d /= 2;

    // Iterate given number of 'k' times
    for (let i = 0; i < k; i++)
        if (!miillerTest(d, n))
            return false;

    return true;
}

Check if a number is prime without using the Sieve of Eratosthenes Complexity Analysis

Time Complexity: O(k * logn)

Iteration Pattern

  • The test runs k times to improve accuracy.
  • In each iteration, it performs Modular Exponentiation, which runs in O(log⁡n) time.
  • Additionally, the loop for squaring runs at most O(log⁡n) times in the worst case.

Recurrence Relation

Let T(n) be the total time required for the test:

  • Each iteration calls the power function, which takes O(log⁡n) time.
  • The squaring loop runs O(log⁡n) times.
  • Since the test runs k times, the total complexity is:

T(n) = k ⋅ O(log⁡n)

Final Time Complexity: O(k * logn)

Space Complexity: O(1)

We use few variables which accumulates to a constant space, hence the total space complexity is O(1).

Solovay-Strassen Test (Using Euler’s Criterion)

Euler’s Criterion provides another way to check for primality based on the Jacobi Symbol. If p is prime:

a^((p-1)/2) ≡ (a/p) mod p

where (a/p) is the Jacobi Symbol (a generalization of the Legendre symbol). If this condition fails, n is composite.

Step-by-Step Example:

Let’s check if 47 is prime:
• Pick a random base, say a = 5.
• Compute 5^((47-1)/2) mod 47.
• Compare it with the Jacobi symbol (5/47).
• If the values don’t match, 47 is composite.
• If they do match for multiple values of a, 47 is probably prime.

Why use this test?

• It provides a good probabilistic test, but Miller-Rabin is generally preferred for efficiency.
• Like Miller-Rabin, running it multiple times increases accuracy.

Check if a number is prime without using the Sieve of Eratosthenes Algorithm (Solovay-Strassen Test)

Handle Base Cases:

  • If n ≤ 1, return false (not prime).
  • If n = 2, return true (prime).
  • If n is even, return false (composite).

Repeat the following steps k times for better accuracy:

  • Pick a random integer a in the range [2, n−2].
  • Compute the Jacobi Symbol (a/n).
  • Compute a^((n-1)/2) mod n using Modular Exponentiation.
  • If the computed values do not match, return false (composite).

If all iterations pass, return true (probably prime).

Check if a number is prime without using the Sieve of Eratosthenes Solution (Solovay-Strassen Test)

 Let's see the Solovay-Strassen Test code in C++, Java, Python and JavaScript.

"Check if a number is prime without using the Sieve of Eratosthenes" Code in all Languages.
1. Check if a number is prime without using the Sieve of Eratosthenes solution in C++ Try on Compiler 
// Modulo function to perform binary exponentiation
long modulo(long base, long exponent, long mod) {
    long x = 1;
    long y = base;

    while (exponent > 0) {
        if (exponent % 2 == 1)
            x = (x * y) % mod;

        y = (y * y) % mod;
        exponent /= 2;
    }
    return x % mod;
}

// Function to calculate the Jacobian symbol of a given number
long calculateJacobian(long a, long n) {
    if (n <= 0 || n % 2 == 0)
        return 0;

    long ans = 1;
    if (a < 0) {

        // (a/n) = (-a/n) * (-1/n)
        a = -a; 
        if (n % 4 == 3)

        // (-1/n) = -1 if n ≡ 3 (mod 4)
            ans = -ans; 
    }
    if (a == 1)

        // (1/n) = 1
        return ans; 

    while (a != 0) {
        if (a < 0) {
            a = -a;
            if (n % 4 == 3)
                ans = -ans;
        }
        while (a % 2 == 0) {
            a /= 2;
            if (n % 8 == 3 || n % 8 == 5)
                ans = -ans;
        }

        long temp = a;
        a = n;
        n = temp;

        if (a % 4 == 3 && n % 4 == 3)
            ans = -ans;

        a %= n;
        if (a > n / 2)
            a -= n;
    }
    return (n == 1) ? ans : 0;
}

// Function to perform the Solovay-Strassen Primality Test
bool solovayStrassen(long p, int iteration) {
    if (p < 2)
        return false;
    if (p != 2 && p % 2 == 0)
        return false;

    for (int i = 0; i < iteration; i++) {
        long a = rand() % (p - 1) + 1;
        long jacobian = (p + calculateJacobian(a, p)) % p;
        long mod = modulo(a, (p - 1) / 2, p);

        if (jacobian == 0 || mod != jacobian)
            return false;
    }
    return true;
}

2. Check if a number is prime without using the Sieve of Eratosthenes Solution in Java Try on Compiler 
// Modulo function to perform binary exponentiation
static long modulo(long base, long exponent, long mod) {
    long x = 1;
    long y = base;

    while (exponent > 0) {
        if (exponent % 2 == 1)
            x = (x * y) % mod;

        y = (y * y) % mod;
        exponent /= 2;
    }
    return x % mod;
}

// Function to calculate the Jacobian symbol of a given number
static long calculateJacobian(long a, long n) {
    if (n <= 0 || n % 2 == 0)
        return 0;

    long ans = 1;
    if (a < 0) {
        a = -a;
        if (n % 4 == 3)
            ans = -ans;
    }
    if (a == 1)
        return ans;

    while (a != 0) {
        if (a < 0) {
            a = -a;
            if (n % 4 == 3)
                ans = -ans;
        }
        while (a % 2 == 0) {
            a /= 2;
            if (n % 8 == 3 || n % 8 == 5)
                ans = -ans;
        }

        long temp = a;
        a = n;
        n = temp;

        if (a % 4 == 3 && n % 4 == 3)
            ans = -ans;

        a %= n;
        if (a > n / 2)
            a -= n;
    }
    return (n == 1) ? ans : 0;
}

// Function to perform the Solovay-Strassen Primality Test
static boolean solovayStrassen(long p, int iteration) {
    if (p < 2)
        return false;
    if (p != 2 && p % 2 == 0)
        return false;

    Random rand = new Random();
    for (int i = 0; i < iteration; i++) {
        long a = 2 + rand.nextInt((int) (p - 2));
        long jacobian = (p + calculateJacobian(a, p)) % p;
        long mod = modulo(a, (p - 1) / 2, p);

        if (jacobian == 0 || mod != jacobian)
            return false;
    }
    return true;
}

3. Check if a number is prime without using the Sieve of Eratosthenes Solution in Python Try on Compiler 
import random

# Modulo function to perform binary exponentiation
def modulo(base, exponent, mod):
    x = 1
    y = base

    while exponent > 0:
        if exponent % 2 == 1:
            x = (x * y) % mod
        y = (y * y) % mod
        exponent //= 2

    return x % mod

# Function to calculate the Jacobian symbol of a given number
def calculate_jacobian(a, n):
    if n <= 0 or n % 2 == 0:
        return 0

    ans = 1
    if a < 0:
        a = -a
        if n % 4 == 3:
            ans = -ans
    if a == 1:
        return ans

    while a != 0:
        if a < 0:
            a = -a
            if n % 4 == 3:
                ans = -ans
        while a % 2 == 0:
            a //= 2
            if n % 8 in [3, 5]:
                ans = -ans

        a, n = n, a

        if a % 4 == 3 and n % 4 == 3:
            ans = -ans

        a %= n
        if a > n // 2:
            a -= n

    return ans if n == 1 else 0

# Function to perform the Solovay-Strassen Primality Test
def solovay_strassen(p, iteration):
    if p < 2 or (p != 2 and p % 2 == 0):
        return False

    for _ in range(iteration):
        a = random.randint(2, p - 2)
        jacobian = (p + calculate_jacobian(a, p)) % p
        mod = modulo(a, (p - 1) // 2, p)

        if jacobian == 0 or mod != jacobian:
            return False

    return True

4. Check if a number is prime without using the Sieve of Eratosthenes solution in JavaScript Try on Compiler 
// Modulo function to perform binary exponentiation
function modulo(base, exponent, mod) {
    let x = 1n;
    let y = base;

    while (exponent > 0n) {
        if (exponent % 2n === 1n)
            x = (x * y) % mod;

        y = (y * y) % mod;
        exponent /= 2n;
    }
    return x % mod;
}

// Function to calculate the Jacobian symbol of a given number
function calculateJacobian(a, n) {
    if (n <= 0n || n % 2n === 0n)
        return 0n;

    let ans = 1n;
    if (a < 0n) {
        a = -a;
        if (n % 4n === 3n)
            ans = -ans;
    }
    if (a === 1n)
        return ans;

    while (a !== 0n) {
        if (a < 0n) {
            a = -a;
            if (n % 4n === 3n)
                ans = -ans;
        }
        while (a % 2n === 0n) {
            a /= 2n;
            if (n % 8n === 3n || n % 8n === 5n)
                ans = -ans;
        }

        let temp = a;
        a = n;
        n = temp;

        if (a % 4n === 3n && n % 4n === 3n)
            ans = -ans;

        a %= n;
        if (a > n / 2n)
            a -= n;
    }
    return (n === 1n) ? ans : 0n;
}

// Function to perform the Solovay-Strassen Primality Test
function solovayStrassen(p, iteration) {
    if (p < 2n)
        return false;
    if (p !== 2n && p % 2n === 0n)
        return false;

    for (let i = 0; i < iteration; i++) {
        let a = BigInt(2 + Math.floor(Math.random() * (Number(p - 2n))));
        let jacobian = (p + calculateJacobian(a, p)) % p;
        let mod = modulo(a, (p - 1n) / 2n, p);

        if (jacobian === 0n || mod !== jacobian)
            return false;
    }
    return true;
}

Check if a number is prime without using the Sieve of Eratosthenes Complexity Analysis

Time Complexity: O(k(logn)2)

Iteration Pattern

The test runs k times for accuracy.
Each iteration performs:

  • Jacobi symbol computation in O((log n)2) time.
  • Modular exponentiation in O(log n) time using Exponentiation by Squaring.

Recurrence Relation

Let T(n) be the time required for the test:
Each iteration takes O((logn)2)+O(logn) = O((logn)2) time.
Since the test runs k times, the total complexity is:

T(n)=k⋅ O((logn)2) = O(k(logn)2)

Final Time Complexity: O(k(logn)2)

Space Complexity: O(1)

We use few variables which accumulates to a constant space, hence the total space complexity is O(1).

Learning Tip

Explore the inbuilt pow function available in C++, Java, Python and JavaScript.

  • Trial Division – Simple but slow for large numbers.
  • Fermat’s Test – Uses modular exponentiation but can give false positives.
  • Miller-Rabin – More reliable than Fermat, widely used in cryptography.
  • Solovay-Strassen – Uses Euler’s Criterion and the Jacobi Symbol.
  • Modular Exponentiation – Use the pow function for efficient calculations.

Real World Example

  • Fast primality tests are essential for cryptography, ensuring secure key generation.
  • Probabilistic methods efficiently verify large primes in encryption algorithms.
  • Advanced techniques speed up primality checks, replacing slow division-based methods in security systems.

Similar Problems

Count Primes

Given an integer n, return the number of prime numbers that are strictly less than n.

Closest Prime Numbers in Range

Given two positive integers left and right, find the two integers num1 and num2 such that:

  • left <= num1 < num2 <= right .
  • Both num1 and num2 are prime numbers.
  • num2 - num1 is the minimum amongst all other pairs satisfying the above conditions.

Return the positive integer array ans = [num1, num2]. If there are multiple pairs satisfying these conditions, return the one with the smallest num1 value. If no such numbers exist, return [-1, -1].