Skip to content

Instantly share code, notes, and snippets.

@zanbaldwin
Created February 16, 2022 12:35
Show Gist options
  • Save zanbaldwin/98c2a22850a3fb3ccd0f20b28c1147d6 to your computer and use it in GitHub Desktop.
Save zanbaldwin/98c2a22850a3fb3ccd0f20b28c1147d6 to your computer and use it in GitHub Desktop.
I did some cool Rust problems and need to store them somewhere.
const MAX: u32 = 1_000_000;
fn main() {
fizzbuzz();
}
struct Definition<'a> {
divisor: u16,
text: &'a str,
}
fn fizzbuzz() {
let definitions: Vec<Definition> = vec![
Definition{divisor: 3, text: "fizz"},
Definition{divisor: 5, text: "buzz"},
];
for i in 1..MAX {
let mask = calculate_bitmap_mask_for_integer(i, &definitions);
let to_print: String = match mask {
0 => i.to_string(),
_ => calculate_words(mask, &definitions),
};
println!("{}", to_print);
}
}
fn calculate_bitmap_mask_for_integer(number: u32, definitions: &Vec<Definition>) -> u16 {
let mut mask: u16 = 0;
let mut i: u16 = 0;
for definition in definitions {
i += 1;
if number % (definition.divisor as u32) == 0 {
mask |= 1 << i;
}
}
mask
}
fn calculate_words(mask: u16, definitions: &Vec<Definition>) -> String{
let mut words: Vec<&str> = vec![];
let mut i: u16 = 0;
for definition in definitions {
i += 1;
if mask & (1 << i) != 0 {
words.push(definition.text);
}
}
words.join(", ")
}
fn main() {
let max: u32 = 1_000_000_000;
primes_sqrt_fact_step_6k(max);
}
// For a MAX of Ten Million
// Total Modulo Calculations: 49,999,995,000,000 (approx fifty trillion)
fn primes(max: u32)
{
let mut prime_count: u32 = 0;
let mut last_prime_calculated: u32 = 0;
for i in 2..=max {
let mut is_prime: bool = true;
for j in 2..i {
if i % j == 0 {
is_prime = false;
break;
}
}
if is_prime {
prime_count += 1;
last_prime_calculated = i;
// println!("Prime #{}: {}", prime_count, last_prime_calculated);
}
}
println!("There are {} prime numbers between 1 and {}.", prime_count, max);
println!("The last prime number calculated before {} was {}.", max, last_prime_calculated);
}
// For a MAX of Ten Million
// Total Modulo Calculations: 1,746,210,133 (just under two billion)
fn primes_sqrt(max: u32)
{
let mut prime_count: u32 = 0;
let mut last_prime_calculated: u32 = 0;
for i in 2..=max {
let mut is_prime: bool = true;
let min_sqrt: u32 = (i as f32).sqrt() as u32;
for j in 2..=min_sqrt {
if i % j == 0 {
is_prime = false;
break;
}
}
if is_prime {
prime_count += 1;
last_prime_calculated = i;
// println!("Prime #{}: {}", prime_count, last_prime_calculated);
}
}
println!("There are {} prime numbers between 1 and {}.", prime_count, max);
println!("The last prime number calculated before {} was {}.", max, last_prime_calculated);
}
// For a MAX of Ten Million
// Total Modulo Calculations: 286,144,938 (less than three-hundred million).
fn primes_sqrt_fact(max: u32)
{
let mut primes: Vec<u32> = vec![];
for i in 2..=max {
let min_sqrt: u32 = (i as f32).sqrt() as u32;
let mut is_prime: bool = true;
for prime in &primes {
if prime > &min_sqrt {
break;
}
if i % prime == 0 {
is_prime = false;
break;
}
}
if is_prime {
primes.push(i);
// println!("Prime #{}: {}", primes.len(), i);
}
}
println!("There are {} prime numbers between 1 and {}.", primes.len(), max);
println!("The last prime number calculated before {} was {}.", max, primes.pop().unwrap());
}
// Using an Iterator (returned from the step_by method) is *MUCH* less efficient than using
// a range, so the efficiency of only evaluating odd numbers only really starts to show when
// the MAX gets towards the billions (!).
fn primes_sqrt_fact_step(max: u32)
{
let mut primes: Vec<u32> = vec![2];
let mut i: u32 = 3;
// Stepping by two in a loop means we only have to evaluate odd numbers, but use
// "loop { i += 2 }" because an Iterator (from step_by method) is much less efficient
// than a Range.
loop {
if i > max { break; }
let min_sqrt: u32 = (i as f32).sqrt() as u32;
let mut is_prime: bool = true;
for prime in &primes {
if prime > &min_sqrt {
break;
}
if i % prime == 0 {
is_prime = false;
break;
}
}
if is_prime {
primes.push(i);
// println!("Prime #{}: {}", primes.len(), i);
}
i += 2;
}
println!("There are {} prime numbers between 1 and {}.", primes.len(), max);
println!("The last prime number calculated before {} was {}.", max, primes.pop().unwrap());
}
fn primes_sqrt_fact_step_6k(max: u32)
{
// Include 2 and 3 in the initial vector because they don't follow the 6k±1 rule.
let mut primes: Vec<u32> = vec![2, 3];
// Start on the next odd number after the last prime number in the initial vector.
let mut i: u32 = 5;
// Stepping by two in a loop means we only have to evaluate odd numbers, but use
// "loop { i += 2 }" because an Iterator (from step_by method) is much less efficient
// than a Range.
while i < max {
// All prime numbers above 3 are in the form 6k±1.
if ((i + 1) % 6 == 0) || ((i - 1) % 6 == 0) {
let min_sqrt: u32 = (i as f32).sqrt() as u32;
let mut is_prime: bool = true;
for prime in &primes {
if prime > &min_sqrt {
break;
}
if i % prime == 0 {
is_prime = false;
break;
}
}
if is_prime {
primes.push(i);
// println!("Prime #{}: {}", primes.len(), i);
}
}
i += 2;
}
println!("There are {} prime numbers between 1 and {}.", primes.len(), max);
println!("The last prime number calculated before {} was {}.", max, primes.pop().unwrap());
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment