Created
February 23, 2020 08:16
-
-
Save o0Ignition0o/d72f9c1b3533047c93401e7bbd5e8275 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
use std::iter; | |
// in order to determine if n is prime | |
// we will use a primality test. | |
// https://en.wikipedia.org/wiki/Primality_test#Pseudocode | |
fn is_prime(n: u128) -> bool { | |
if n <= 3 { | |
n > 1 | |
} else if n % 2 == 0 || n % 3 == 0 { | |
false | |
} else { | |
for i in (5..=(n as f64).sqrt() as u128).step_by(6) { | |
if n % i == 0 || n % (i + 2) == 0 { | |
return false; | |
} | |
} | |
true | |
} | |
} | |
// given a sequence of digits, return the corresponding number | |
// eg: assert_eq!(1234, digits_to_number(vec![1,2,3,4])) | |
fn digits_to_number(iter: impl Iterator<Item = usize>) -> u128 { | |
iter.fold(0, |acc, b| acc * 10 + b as u128) | |
} | |
fn get_min_bound(num_digits: usize) -> u128 { | |
let lower_bound_iter = | |
iter::once(1usize).chain(iter::repeat(0usize).take(num_digits - 1 as usize)); | |
digits_to_number(lower_bound_iter) | |
} | |
fn get_max_bound(num_digits: usize) -> u128 { | |
let lower_bound_iter = iter::once(1usize).chain(iter::repeat(0usize).take(num_digits)); | |
digits_to_number(lower_bound_iter) | |
} | |
fn number_or_panic(number_to_return: u128) -> u128 { | |
// Let's roll a dice | |
if rand::random::<u8>() % 6 == 0 { | |
panic!(format!( | |
"I was about to return {} but I chose to panic instead!", | |
number_to_return | |
)) | |
} | |
number_to_return | |
} | |
fn get_prime(num_digits: usize) -> u128 { | |
let min_bound = get_min_bound(num_digits); | |
// with num_digits = 4, max_bound == 10000 | |
let max_bound = get_max_bound(num_digits); | |
// maybe_prime is a number in range [1000, 10000) | |
// the closing parenthesiss means it won't reach the number. | |
// the maximum allowed value for maybe_prime is 9999. | |
use rand::Rng; | |
let mut maybe_prime = rand::thread_rng().gen_range(min_bound, max_bound); | |
loop { | |
if is_prime(maybe_prime) { | |
return number_or_panic(maybe_prime); | |
} | |
// for any integer n > 3, | |
// there always exists at least one prime number p | |
// with n < p < 2n - 2 | |
maybe_prime += 1; | |
// We don't want to return a number | |
// that doesn't have the right number of digits | |
if maybe_prime == max_bound { | |
maybe_prime = min_bound; | |
} | |
} | |
} | |
async fn prime_number(req: tide::Request<()>) -> String { | |
use std::time::Instant; | |
let d: usize = req.param("digits").unwrap_or(1); | |
// Start a stopwatch | |
let start = Instant::now(); | |
// Get a prime number | |
let prime_number = get_prime(d); | |
// Stop the stopwatch | |
let elapsed = Instant::now().duration_since(start).as_secs(); | |
format!( | |
"{} is a prime number with {} digits.\nIt was computed in {} seconds.\n", | |
prime_number, d, elapsed | |
) | |
} | |
fn main() -> Result<(), std::io::Error> { | |
use async_std::task; | |
task::block_on(async { | |
let mut app = tide::new(); | |
app.at("/prime/:digits").get(prime_number); | |
app.listen("127.0.0.1:8080").await?; | |
Ok(()) | |
}) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment