Primes ≤ 100 in Rust
Posted by Michał ‘mina86’ Nazarewicz on 20th of June 2021 | (cite)
In a past life I’ve talked about a challenge to write the shortest program which prints all prime numbers less than a hundred. Back then I’ve discussed a 60-character long solution written in C. Since Rust is the future, inspired by a recent thread on Sieve of Eratosthenes I’ve decided to carry the task for Rust as well.
To avoid spoiling the solution, I’m padding this article with a bit of unrelated content. To jump straight to the code, skip the next block of paragraphs. Otherwise, here’s a joke for ya:
After realising he got lost, a man in a hot air balloon spotted a woman below. He descended and shouted, ‘Excuse me, can you help me? I’ve promised a friend I would meet him an hour ago, but I don’t know where I am.’
The woman below looked up and replied matter-of-factly, ‘You are in a hot air balloon hovering around ten metres above the ground. You are between 47 and 48 degrees north latitude and between 8 and 9 degrees east longitude.’
‘You must be an engineer,’ the balloonist concluded.
‘I am,’ the woman replied intrigued, ‘How did you know?’
‘Well, everything you told me is technically correct, but I have no idea how to use your information and I am still lost. Frankly, you’ve not been much help.’
The woman pondered for a while and responded, ‘You must be in management.’
‘I am,’ the man confirmed, ‘but how did you know?’
‘Well, you don’t know where you are or where you are going, you have risen to where you are thanks to hot air, you made a promise which you have no idea how to keep and you expect people beneath you to solve your problems. The fact is you are in exactly the same position you were in before we met, but now, somehow, it’s my fault!’
The solution
Now back to the matter at hand. Let’s first go with a 67-character long solution I came up with. It is as follows:
fn main(){for n in 2..99{if(2..n).all(|k|n%k!=0){println!("{n}")}}}
For comparison, here’s the aforementioned C variant:
main(i,j){for(;j=++i<99;j<i||printf("%d\n",i))for(;i%++j;);}
Let’s break it down a little taking this opportunity to talk about Rust.
Commonality between the two variants is lack of type declarations. It’s important to note that, while in C this was due to (since deprecated) rule that variables are implicitly integers, Rust performs type inference. In many situations in Rust there’s no need to declare types and the compiler will figure out the correct ones.
Rust doesn’t have a C-style for
syntax and offers range loop instead. for n in 2..99 { body }
will execute body with n
variable ranging from 2 to 98 inclusively. Since 99 is not a prime, we don’t need to include it in the range. By the way, 2..99
is not part of the syntax for the loop; rather, it declares a range object. And yes, ranges are right-open (though there’s also syntax for closed intervals).
|args| expr
is Rust’s syntax for lambdas (also known as anonymous functions). I’m not a fan of the pipe characters in there — I’d much rather have Haskell’s syntax instead — but it’s something one can get used to.
The n % k != 0
expression demonstrates Rust doesn’t implicitly convert integers to booleans. In fact, the exclamation mark unary operator performs binary (not logical) negation when applied to integer types. That’s something tilde does in C. Tilde used to declare boxed types and values in Rust but is now unused.
Perhaps due to quirk of history, ranges in Rust are iterators (as opposed to merely implementing IntoIterator
trait) which means that methods such as all
are available on them. all
, of course, checks whether all elements satisfy the predicate given as an argument. This means that (2..n).all(predicate)
will test the predicate for all integers from 2 to n-1 inclusively (again, ranges are right-open unless different operator is used).
And finally, println!
is rather self-explanatory. Since format_args_implicits
feature is now stable, the "{n}"
syntax can be used to save one character. This is something Python programmers should be familiar with though in Rust the f
sigil is not necessary. Programmer needs to know from context when "{n}"
means string interpolation and when it’s a plain string literal.
66-character solution?
There is a way to reach 66 characters. It’s much more boring and I’m not sure if it’s in the spirit of the challenge. The trick is to hard-code the list of primes as a byte buffer. It’s not pretty, but it works:
fn main(){for n in b"\r%)+/5;=CGIOSYa"{println!("{n}")}}
Note that your user agent may fail to display control characters present in the above listing. Copying and pasting should work though.
The b
sigil in front of the string is necessary to declare a byte-array rather than a str
object. The latter cannot be iterated over without invoking bytes
or chars
method which would make the solution too long.