Calculate all the prime numbers between two given numbers

Question

I've made an application that calculates all the prime numbers between two given numbers and prints then into a .txt document... anything I can improve?

use std::io;
use std::fs::{OpenOptions};
use std::io::{Write, BufWriter};

fn main() {

    loop{
        
        let mut format = 1;

        let mut input = String::new();
        println!("Say a start for the prime loop! ");
        
        io::stdin().read_line(&mut input).unwrap();
        let start: u128 = input.trim().parse().unwrap();
        

        let mut input = String::new();
        println!("Say an end for the prime loop! ");       

        io::stdin().read_line(&mut input).unwrap();
        let end: u128 = input.trim().parse().unwrap();

        
        let path = "path/to/file.txt";

        let f = OpenOptions::new()
            .write(true)
            .open(path)
            .expect("Could not open file");

        let mut f = BufWriter::new(f);

        for i in start..end{    
            if prime(i) == true{
                f.write_all(i.to_string().as_bytes()).expect("unable to write to file");
                f.write_all(b"\t").expect("unable to write to file");
                format += 1;
            }
            
            if format == 10{
                f.write_all(b"\n").expect("unable to write to file");
                format = 0;
            }
            
        }
    }
}


fn prime(x: u128) -> bool {

    if x == 4 || x == 6 || x == 8 || x == 9{ //The loop doesnt quite work for numbers below 10 so this is for those numbers
        return false; 
    }
    for i in 2..((x as f64).sqrt() as u128){   
        if x % i == 0 { return false; }  //modulo to see if the number is dividable by variable i
    }
    true
}
```

Answer 1

In addition to l0b0's answer:

The formatting is inconsistent. You can run cargo fmt to clean it up.

Personally, I prefer to rewrite the use declaration in a tree-like manner:

use std::{
    fs::OpenOptions,
    io::{self, BufWriter, Write},
};

The path can be made into a const:

const PATH: &str = "path/to/file.txt";

format is not a descriptive name.

A helper function simplifies the input process by eliminating the code duplication.

---

Here's a modified version, using the sieve of Eratosthenes:

use {
    anyhow::Result,
    bitvec::prelude::*,
    itertools::Itertools,
    std::{
        fs::File,
        io::{self, prelude::*},
        ops::Range,
    },
};

const PATH: &str = "path/to/file.txt";
const N_COLUMNS: usize = 10;

fn main() -> Result<()> {
    let start = input("Enter start of range: ")?;
    let end = input("Enter end of range: ")?;

    let table = sieve_to(end);

    write_primes(&table, start..end)?;

    Ok(())
}

fn sieve_to(end: usize) -> BitVec {
    let mut table = bitvec![1; end];

    // set table[0] and table[1] to false
    for cell in table.iter_mut().take(2) {
        cell.set(false);
    }

    // floor(sqrt(end))
    let limit = num::integer::sqrt(end);

    for number in 2..limit {
        if !table[number] {
            continue;
        }
        for multiple in (number..end).step_by(number).skip(1) {
            table.set(multiple, false);
        }
    }

    table
}

fn input(message: &str) -> Result<usize> {
    eprint!("{}", message);

    let mut line = String::new();
    io::stdin().read_line(&mut line)?;

    Ok(line.trim().parse()?)
}

fn write_primes(table: &BitSlice, range: Range<usize>) -> Result<()> {
    let mut file = File::create(PATH)?;

    writeln!(
        file,
        "{}",
        range
            .filter(|&n| table[n])
            .chunks(N_COLUMNS)
            .into_iter()
            .map(|row| row.format("\t"))
            .format("\n"),
    )?;

    Ok(())
}

Cargo.toml:

[package]
name = "prime"
version = "0.1.0"
authors = ["L. F."]
edition = "2018"

[dependencies]
anyhow = "1.0"
bitvec = "0.20"
itertools = "0.9"
num = "0.3"

I limited the program to one loop per execution, since overwriting the same file again and again does not seem useful to me.

Answer 2

The efficiency of the prime function is probably the most interesting aspect of this exercise. You're limiting the search space to up to the square root of the number, which is good, but the fact that you're looking for all primes in a range would make many other prime searching algorithms usable, such as the Sieve of Eratosthenes, which fairly efficiently gets you the primes from 2 through N. The issue is that which algorithm to use in your case depends on runtime inputs: if the user asks for prime numbers between 2 and a large N there are heaps of efficient algorithms. If they instead ask for primes between a large N and N+1 it probably makes much more sense to just look at those two numbers. I'm not a mathematician, but choosing which algorithm to use depending on the range seems like a subject worth studying.

I don't see why the algorithm would not work for numbers 4, 6, 8 and 9 - that seems like either a subtle bug in the loop or just a misunderstanding. I would add some test cases to prime and verify it with lots of different inputs.

prime takes a u128, but then drops precision when converting it to f64 before taking the square root. Since Integer -> Float -> Integer conversion can succeed while changing what the value is, I suspect there are corner cases where the range is miscalculated. See also this discussion.