Primality Test

Definition

Definition

The Primality Test Algorithm is a method used to determine whether a given integer is prime or not. It involves evaluating the divisibility of the number by smaller integers to ascertain if it has any factors other than 1 and itself. The algorithm leverages efficient techniques to minimize computational complexity

Explanation

Checking whether the given number n is divisible by any integer other than 1 and itself. It begins by testing divisibility with 2, then proceeds to check odd integers up to the square root of n. If n is divisible by any of these integers, it is deemed composite; otherwise, it is considered prime.

Guidance

• Start by checking if the given number is less than 2. If so, it cannot be prime
• If the number is 2, it is prime
• Check if the number is divisible by 2. If yes, it is not prime
• Iterate through odd numbers starting from 3 up to the square root of the given number
• For each odd number, check if the given number is divisible by it. If yes, it is not prime
• If none of the above conditions are met, the number is prime

Tips

• utilize efficient techniques such as checking divisibility only up to the square root of the given number to minimize computational complexity
• implement optimizations like skipping even numbers greater than 2 in the iteration process since they cannot be prime

Practice

Practice

isPrime(n):
  if n < 2:
    return false
  if n == 2:
    return true
  if n % 2 == 0:
    return false
  limit = floor(sqrt(n))
  for i = 3 to limit step 2:
    if n % i == 0:
      return false
  return true

Solution

package main

import (
    "math"
)

func trialDivision(number int) bool {
    if number <= 1 || (number%2 == 0 && number != 2) {
        return false
    }

    dividerLimit := int(math.Sqrt(float64(number)))
    for divider := 3; divider <= dividerLimit; divider += 2 {
        if number%divider == 0 {
            return false
        }
    }

    return true
}

public class Main {

  public static boolean trialDivision(int number) {
    if (number <= 1 || (number % 2 == 0 && number != 2)) {
      return false;
    }

    int dividerLimit = (int) Math.sqrt(number);
    for (int divider = 3; divider <= dividerLimit; divider += 2) {
      if (number % divider == 0) {
        return false;
      }
    }

    return true;
  }
}

function trialDivision(number) {
  if (number <= 1 || (number % 2 === 0 && number !== 2)) {
    return false;
  }

  const dividerLimit = Math.sqrt(number);
  for (let divider = 3; divider <= dividerLimit; divider += 2) {
    if (number % divider === 0) {
      return false;
    }
  }

  return true;
}

fun trialDivision(number: Int): Boolean {
    if (number <= 1 || (number % 2 == 0 && number != 2)) {
        return false
    }

    val dividerLimit = Math.sqrt(number.toDouble()).toInt()
    for (divider in 3..dividerLimit step 2) {
        if (number % divider == 0) {
            return false
        }
    }

    return true
}

import math

def trialDivision(number):
    if number <= 1 or (number % 2 == 0 and number != 2):
        return False

    dividerLimit = int(math.sqrt(number))
    for divider in range(3, dividerLimit + 1, 2):
        if number % divider == 0:
            return False

    return True

fn trial_division(number: u32) -> bool {
    if number <= 1 || (number % 2 == 0 && number != 2) {
        return false;
    }

    let divider_limit = (number as f64).sqrt() as u32;
    for divider in (3..=divider_limit).step_by(2) {
        if number % divider == 0 {
            return false;
        }
    }

    true
}

function trialDivision(number: number): boolean {
  if (number <= 1 || (number % 2 === 0 && number !== 2)) {
    return false;
  }

  const dividerLimit = Math.sqrt(number);
  for (let divider = 3; divider <= dividerLimit; divider += 2) {
    if (number % divider === 0) {
      return false;
    }
  }

  return true;
}