Write a program

[juntao]

Can you write a Rust function that checks if an input integer is a prime number?

[alabulei1]

Sure! Here's a Rust function that checks if an input integer is a prime number:

fn is_prime(num: i32) -> bool {
    if num <= 1 {
        return false;
    }
    for i in 2..num {
        if num % i == 0 {
            return false;
        }
    }
    return true;
}

You can call this function with an integer as its argument, and it'll return true if the number is a prime, and false otherwise. For example:

assert_eq!(is_prime(5), true);
assert_eq!(is_prime(6), false);

In this example, the first assertion would pass because 5 is a prime number, while the second assertion would fail because 6 is not a prime number.

[juntao]

But, you do not need to check for all the even numbers!

[alabulei1]

You're right! We can optimize the function by only checking for divisibility by odd numbers after we've ensured that the number is greater than 2. Here is an updated version of the function:

fn is_prime(num: i32) -> bool {
    if num <= 1 {
        return false;
    }
    if num == 2 {
        return true;
    }
    if num % 2 == 0 {
        return false;
    }
    let mut i = 3;
    while i * i <= num {
        if num % i == 0 {
            return false;
        }
        i += 2;
    }
    return true;
}

In this version of the function, we first check if the input number is less than or equal to 1, and return false in that case. If the number is equal to 2, we return true, as 2 is prime. Next, we check if the number is even (if it's divisible by 2) and return false in that case as well. Finally, we iterate through odd numbers starting from 3 and check if the input number is divisible by any of them. If the number is not divisible by any odd number up to its square root, we return true, indicating that the number is prime.

[juntao]

That's better. But you do not need to check for multiples of all the prime numbers you discovered earlier in the loop!

[alabulei1]

You're right again! We can further optimize the function by only checking for divisibility by prime numbers up to the square root of the input number. Here's the updated version of the function:

fn is_prime(num: i32) -> bool {
    if num <= 1 {
        return false;
    }
    if num == 2 {
        return true;
    }
    if num % 2 == 0 {
        return false;
    }
    let mut i = 3;
    while i * i <= num {
        if num % i == 0 {
            return false;
        }
        i += 2;
        let mut is_prime = true;
        for factor in 3..((i as f32).sqrt() as i32) + 1 {
            if i % factor == 0 {
                is_prime = false;
                break;
            }
        }
        if is_prime {
            if num % i == 0 {
                return false;
            }
        }
    }
    return true;
}

In this version, we still start with the same initial checks for numbers less than or equal to 1, equal to 2, or divisible by 2. However, instead of checking all odd numbers up to the square root of the input number, we only check the prime numbers in that range. For each odd number i, we iterate through prime numbers up to sqrt(i), checking if i is divisible by any of them. If i is found to be not divisible by any prime number up to sqrt(i), we check if the input number is divisible by i, and return false if it is. If none of the odd numbers up to sqrt(num) divide num evenly, we return true, indicating that the number is prime.

[juntao]

I think it is inefficient. Isn't it better to store all the prime numbers as you check them for use later?

[alabulei1]

Yes, that's a good suggestion! Caching previously computed prime numbers can make the function more efficient, as we only need to check if the input number is divisible by prime numbers that we've already discovered. Here's the updated version of the function that uses caching:

fn is_prime(num: i32) -> bool {
    if num <= 1 {
        return false;
    }
    if num == 2 {
        return true;
    }
    if num % 2 == 0 {
        return false;
    }
    let mut primes = vec![2];
    let mut i = 3;
    while i * i <= num {
        let is_prime = primes.iter().all(|p| i % p != 0);
        if is_prime {
            primes.push(i);
            if num % i == 0 {
                return false;
            }
        }
        i += 2;
    }
    for p in primes.iter() {
        if num % p == 0 {
            return false;
        }
    }
    true
}

In this version of the function, we start with the same initial checks for numbers less than or equal to 1, equal to 2, or divisible by 2. Then we create an empty vector called primes to store previously computed prime numbers. We start iterating from the number 3 and check if each odd number is a prime. If the number is a prime, we add it to the primes vector, and check if it divides the input number evenly. If it does, we return false, indicating that the number is not prime.

Finally, we iterate through all prime numbers that we've discovered so far, and check if each one is a factor of the input number. If any prime number is found to be a factor of the input number, we return false, as the input number is not prime. If we reach the end of the loop and none of the primes divide the input number evenly, we return true, indicating that the number is prime.