Primes ≤ 100 in Rust

Posted by Michał ‘mina86’ Nazarewicz on 20th of June 2021

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 68-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 the correct one out.

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 dosn’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 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. For people interested in the future, it’s worth noting that if format_args_implicits feature gets stabilised, the code will be shortened by one more character.

67-character solution?

There is a way to reach 67 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 doesn’t cannot be iterated over without invoking bytes or chars method which would make the solution too long.