New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Write a program #250
Comments
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 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. |
But, you do not need to check for all the even numbers! |
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 |
That's better. But you do not need to check for multiples of all the prime numbers you discovered earlier in the loop! |
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 think it is inefficient. Isn't it better to store all the prime numbers as you check them for use later? |
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 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 |
Can you write a Rust function that checks if an input integer is a prime number?
The text was updated successfully, but these errors were encountered: