# Calculate all the prime numbers between two given numbers

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! ");

let start: u128 = input.trim().parse().unwrap();

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

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
}
$$$$

• Different algorithms would need to be used depending on the size of the upper bound as well as the size of the interval. It's worth keeping in mind that there are at least 2**120 primes between 2**127 and 2**128. Dec 26 '20 at 17:42

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();

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.

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.

• I believe the square root function doesn't work so good on low numbers... it messes up the for loop too, I could probably fix that but I should try to work on algorithms like you said, Thanks for the reply! You're one of the first actual nice people on here... Dec 26 '20 at 1:48
• Which one you should work on depends on the goal of the code, but if you really want to support massive numbers like u128 there's probably a lot of work before the code is as stable and performant as possible.
– l0b0
Dec 26 '20 at 2:22
• Also, re. nice people, it's a tricky one. Sooo much has been written about this, but I'll just say that text is terrible for communicating feeling, and a lot of users, because they value their time, end up optimizing for terseness when answering. This can often be seen as not very nice, especially when that terseness comes simply in the form of a downvote, close vote, or a quick comment to make the question answerable. On the other hand, experienced users are often triggered by new users not following the guidelines, and effectively wasting everybody's time.
– l0b0
Dec 26 '20 at 3:21