Pure Programmer
Project: Number of Primes
The number of primes equal to or less than a number x is denoted by the function `π(x)`. There is no easy way to compute this function although there are ways to compute a list of primes. Use the SieveOfEratosthenes project to generate a file of prime numbers less than 1,000,000. Then write a function `π(x)` that searches the file for the answer. The function should return the number of primes read before a value greater than x is found. To improve efficiency for subsequent calls to `π(x)` you should only read the file the first time the function is called and store the prime values in an array. This way subsequent calls to `π(x)` don't need to re-read the file. Write a test program to print the values of `π(x)` for x that are powers of 2 up to `2^19`. Will this approach work if you want to compute values for x up to 1,000,000,000 by generating an approprite file of primes? Modify the program to use an estimate `x/(ln x - 1)` for values greater than are found in the primes data file. Test by computing `π(x)` up to `2^30`.
See [[How Many Primes Are There?]] See SieveOfEratosthenes
Output
$ rustc NumberOfPrimes.rs
error: unknown format trait `d`
--> NumberOfPrimes.rs:69:34
|
69 | println!("{}", format!("π({0:d}) = {1:d}", x, π(x)));
| ^
|
= note: the only appropriate formatting traits are:
- ``, which uses the `Display` trait
- `?`, which uses the `Debug` trait
- `e`, which uses the `LowerExp` trait
- `E`, which uses the `UpperExp` trait
- `o`, which uses the `Octal` trait
- `p`, which uses the `Pointer` trait
- `b`, which uses the `Binary` trait
- `x`, which uses the `LowerHex` trait
- `X`, which uses the `UpperHex` trait
error: unknown format trait `d`
--> NumberOfPrimes.rs:69:43
|
69 | println!("{}", format!("π({0:d}) = {1:d}", x, π(x)));
| ^
|
= note: the only appropriate formatting traits are:
- ``, which uses the `Display` trait
- `?`, which uses the `Debug` trait
- `e`, which uses the `LowerExp` trait
- `E`, which uses the `UpperExp` trait
- `o`, which uses the `Octal` trait
- `p`, which uses the `Pointer` trait
- `b`, which uses the `Binary` trait
- `x`, which uses the `LowerHex` trait
- `X`, which uses the `UpperHex` trait
error[E0425]: cannot find value `ifh` in this scope
--> NumberOfPrimes.rs:16:11
|
16 | utf8mode(ifh);
| ^^^ not found in this scope
error[E0425]: cannot find value `ifh` in this scope
--> NumberOfPrimes.rs:18:21
|
18 | while getline(line,ifh) {
| ^^^ not found in this scope
error[E0425]: cannot find value `Utils` in this scope
--> NumberOfPrimes.rs:19:21
|
19 | let mut p:isize = Utils.stoiWithDefault(line, 0);
| ^^^^^ not found in this scope
error[E0425]: cannot find value `ifh` in this scope
--> NumberOfPrimes.rs:24:8
|
24 | close(ifh);
| ^^^ not found in this scope
warning: the usage of Script Group `Greek` in this crate consists solely of mixed script confusables
--> NumberOfPrimes.rs:49:4
|
49 | fn π(x:isize) -> i64 {
| ^
|
= note: the usage includes 'π' (U+03C0)
= note: please recheck to make sure their usages are indeed what you want
= note: `#[warn(mixed_script_confusables)]` on by default
error[E0425]: cannot find function `utf8mode` in this scope
--> NumberOfPrimes.rs:16:2
|
16 | utf8mode(ifh);
| ^^^^^^^^ not found in this scope
error[E0425]: cannot find function `getline` in this scope
--> NumberOfPrimes.rs:18:8
|
18 | while getline(line,ifh) {
| ^^^^^^^ not found in this scope
error[E0425]: cannot find function `close` in this scope
--> NumberOfPrimes.rs:24:2
|
24 | close(ifh);
| ^^^^^ not found in this scope
error[E0308]: mismatched types
--> NumberOfPrimes.rs:14:33
|
14 | fn readPrimes(filename:&str) -> Result<(), Arc<dyn error::Error>> {
| ---------- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected `Result<(), Arc<dyn Error>>`, found `()`
| |
| implicitly returns `()` as its body has no tail or `return` expression
|
= note: expected enum `Result<(), Arc<(dyn std::error::Error + 'static)>>`
found unit type `()`
error[E0308]: mismatched types
--> NumberOfPrimes.rs:28:13
|
28 | if value < primes.first().unwrap() {
| ----- ^^^^^^^^^^^^^^^^^^^^^^^ expected `isize`, found `&isize`
| |
| expected because this is `isize`
|
help: consider dereferencing the borrow
|
28 | if value < *primes.first().unwrap() {
| +
error[E0308]: mismatched types
--> NumberOfPrimes.rs:31:13
|
31 | if value > primes.last().unwrap() {
| ----- ^^^^^^^^^^^^^^^^^^^^^^ expected `isize`, found `&isize`
| |
| expected because this is `isize`
|
help: consider dereferencing the borrow
|
31 | if value > *primes.last().unwrap() {
| +
error[E0308]: mismatched types
--> NumberOfPrimes.rs:32:10
|
27 | fn binarySearch(list:Vec<isize>, value:isize) -> isize {
| ----- expected `isize` because of return type
...
32 | return primes.len();
| ^^^^^^^^^^^^ expected `isize`, found `usize`
|
help: you can convert a `usize` to an `isize` and panic if the converted value doesn't fit
|
32 | return primes.len().try_into().unwrap();
| ++++++++++++++++++++
error[E0308]: mismatched types
--> NumberOfPrimes.rs:35:24
|
35 | let mut right:isize = list.len() - 1;
| ----- ^^^^^^^^^^^^^^ expected `isize`, found `usize`
| |
| expected due to this
|
help: you can convert a `usize` to an `isize` and panic if the converted value doesn't fit
|
35 | let mut right:isize = (list.len() - 1).try_into().unwrap();
| + +++++++++++++++++++++
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> NumberOfPrimes.rs:38:11
|
38 | if list[m] < value {
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> NumberOfPrimes.rs:40:18
|
40 | } else if list[m] > value {
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0308]: mismatched types
--> NumberOfPrimes.rs:50:22
|
50 | let mut pos:isize = primes.len();
| ----- ^^^^^^^^^^^^ expected `isize`, found `usize`
| |
| expected due to this
|
help: you can convert a `usize` to an `isize` and panic if the converted value doesn't fit
|
50 | let mut pos:isize = primes.len().try_into().unwrap();
| ++++++++++++++++++++
error[E0308]: mismatched types
--> NumberOfPrimes.rs:54:12
|
54 | if pos == primes.len() {
| --- ^^^^^^^^^^^^ expected `isize`, found `usize`
| |
| expected because this is `isize`
|
help: you can convert a `usize` to an `isize` and panic if the converted value doesn't fit
|
54 | if pos == primes.len().try_into().unwrap() {
| ++++++++++++++++++++
error[E0277]: the trait bound `f64: From<isize>` is not satisfied
--> NumberOfPrimes.rs:55:27
|
55 | return (round(f64::from(x) / (log((x) as f64) - 1))) as i64;
| --------- ^ the trait `From<isize>` is not implemented for `f64`
| |
| required by a bound introduced by this call
|
= help: the following other types implement trait `From<T>`:
<f64 as From<bool>>
<f64 as From<f32>>
<f64 as From<i16>>
<f64 as From<i32>>
<f64 as From<i8>>
<f64 as From<u16>>
<f64 as From<u32>>
<f64 as From<u8>>
error[E0061]: this function takes 1 argument but 0 arguments were supplied
--> NumberOfPrimes.rs:55:33
|
55 | return (round(f64::from(x) / (log((x) as f64) - 1))) as i64;
| ^^^ an argument of type `f64` is missing
|
note: method defined here
--> /opt/local/libexec/rust/src/rustc-1.71.1-src/library/std/src/f64.rs:482:12
help: provide the argument
|
55 | return (round(f64::from(x) / (log(/* f64 */)((x) as f64) - 1))) as i64;
| +++++++++++
error[E0425]: cannot find function `log` in this scope
--> NumberOfPrimes.rs:55:33
|
55 | return (round(f64::from(x) / (log((x) as f64) - 1))) as i64;
| ^^^ not found in this scope
|
help: use the `.` operator to call the method `log` on `f64`
|
55 | return (round(f64::from(x) / (((x) as f64).log() - 1))) as i64;
| ~ ~~~~~~~
error[E0277]: cannot subtract `{integer}` from `f64`
--> NumberOfPrimes.rs:55:49
|
55 | return (round(f64::from(x) / (log((x) as f64) - 1))) as i64;
| ^ no implementation for `f64 - {integer}`
|
= help: the trait `Sub<{integer}>` is not implemented for `f64`
= help: the following other types implement trait `Sub<Rhs>`:
<&'a f64 as Sub<f64>>
<&f64 as Sub<&f64>>
<f64 as Sub<&f64>>
<f64 as Sub>
help: consider using a floating-point literal by writing it with `.0`
|
55 | return (round(f64::from(x) / (log((x) as f64) - 1.0))) as i64;
| ++
error[E0425]: cannot find function `round` in this scope
--> NumberOfPrimes.rs:55:11
|
55 | return (round(f64::from(x) / (log((x) as f64) - 1))) as i64;
| ^^^^^ not found in this scope
|
help: use the `.` operator to call the method `StdFloat::round` on `{type error}`
|
55 | return ((f64::from(x) / (log((x) as f64) - 1)).round() as i64;
| ~ ~~~~~~~~~
error: aborting due to 23 previous errors; 1 warning emitted
Some errors have detailed explanations: E0061, E0277, E0308, E0425.
For more information about an error, try `rustc --explain E0061`.