How can prime numbers be efficiently determined? Economy 100 ms for 100 numbers.

How to improve the time complexity of number primality testing from O(sqrt(n)) to O(k * log³(n)), where k is a constant factor.

A prime number, is a natural number greater than 1 that has no positive divisors other than 1 and itself. In other words, it cannot be formed by multiplying two smaller natural numbers. Conversely, a natural number greater than 1 that is not prime is termed a composite number, meaning it can be expressed as the product of at least two smaller natural numbers.

First of all, let’s examine a straightforward implementation for testing the primality of a number with time complexity of O(sqrt(n)).

let is_prime = |val: i32| -> bool {
    if val <= 1 {
      return false;
    }
    let lim = (val as f64).sqrt() as i32;
    for i in 2..lim {
      if val % i == 0 {
        return false;
      }
    }
    true
};

But, a faster way to check for primality is to use the Miller-Rabin primality test, which has a time complexity of O(k * log³(n)), where k is the number of rounds performed by the test.

let is_prime = |val: i32| -> bool {
    if val <= 1 {
        return false;
    }
    if val == 2 || val == 3 {
        return true;
    }
    if val % 2 == 0 || val % 3 == 0 {
        return false;
    }

    let mut i = 5;
    while i * i <= val {
        if val % i == 0 || val % (i + 2) == 0 {
            return false;
        }
        i += 6;
    }

    true
};

Example: return the largest prime number that lies on at least one of the diagonals of numbers.

use std::cmp::max;

impl Solution {
    pub fn diagonal_prime(nums: &[[i32;10];10]) -> i32 { 

        let mut max_prime = 0;
        let n = nums.len();

        for i in 0..n {
            if is_prime(nums[i][i]) {
                max_prime = max(max_prime, nums[i][i]);
            }
            if is_prime(nums[n-i-1][i]) {
                max_prime = max(max_prime, nums[n-i-1][i]);
            }
        }

        max_prime
    }
}

const Numbers: [[i32; 10]; 10] = [[677088, 756354, 492839, 227615, 196834, 693183, 603728, 53790, 656614, 263593],
                             [657275, 194338, 330005, 154392, 227021, 80083, 97051, 926094, 625679, 231202],
                             [394311, 16003, 488746, 248824, 661276, 214428, 420300, 531563, 420780, 114044],
                             [802351, 209178, 275295, 270157, 827164, 742318, 841087, 212639, 417264, 28208], 
                             [265454, 75828, 165275, 458482, 300340, 517189, 595089, 624238, 336350, 715312], 
                             [879771, 520689, 173756, 870268, 725374, 706725, 685477, 336304, 737464, 594003], 
                             [136204, 569886, 245751, 474317, 660913, 20850, 678631, 875101, 413808, 732613], 
                             [881063, 318444, 114326, 667715, 64990, 879314, 862775, 559645, 827115, 655380], 
                             [962480, 235156, 670639, 730846, 993113, 628558, 445653, 506482, 213848, 16632], 
                             [432462, 439426, 523451, 499208, 814931, 937398, 768253, 999100, 644609, 378968]];
fn main() { 
    let max_prime = Solution::diagonal_prime(&Numbers);

    println!("Max prime number is {max_prime}");
}

Timing for 100 array elements

O(sqrt(n)) ................................................. 0.45s

O(k * log³(n)).............................................. 0.38s

As we can see a substantial speed improvement with the second approach of checking that the number is prime.

Thank you for accompanying me on this journey through the realm of prime numbers. All the best to you as you continue to explore, learn, and discover the wonders that the world of programming has to offer.