# Rust How can I set an upper limit for a for statement?

``````for (long long i = 1; i * i <= n; i++)
``````

In C++ it is represented by the above code, but how should it be represented in Rust?

``````for i in 1..=n{

}
``````

`(1..).take_while(|i| i * i <= n)` should do the trick.

You could also just write a manual while loop that's the equivalent of the C code, but it would be less readable and less idiomatic:

``````let mut i = 1;
while i * i <= n {
... do stuff ...
i += 1;
}
``````
3 Likes

I used to write this way in C++, how do you recommend I write Rust?

``````vector<long long> divisor(long long n) {
vector<long long> ret;
for (long long i = 1; i * i <= n; i++) {
if (n % i == 0) {
ret.push_back(i);
if (i * i != n) ret.push_back(n / i);
}
}
sort(ret.begin(), ret.end());
return ret;
}
``````

A quite literal translation could look like this

``````fn divisor(n: u64) -> Vec<u64> {
let mut ret = vec![];
for i in (1..).take_while(|i| i * i <= n) {
if n % i == 0 {
ret.push(i);
if i * i != n {
ret.push(n / i)
}
}
}
ret.sort();
ret
}
``````

both the C++ code and the Rust code might have a problem with `i * i` overflowing if `n` is close to `u64::MAX`, I havenâ€™t thought this through or tested it yet though, but at least in Rust there would not be undefined behavior in case of overflow.

1 Like

To avoid overflow, you could use `1..(1 << 32)`. Or you could compute the integer `sqrt(n)` ahead of time and use that as the limit, and then you don't need `take_while` at all.

1 Like

In terms of different-looking code following the same control flow / logic in principle AFAICT, I could come up with something like

``````fn divisor(n: u64) -> Vec<u64> {
let mut ret: Vec<u64> = (1..)
.take_while(|i| i * i <= n)
.filter(|i| n % i == 0)
.flat_map(|i| std::iter::once(i).chain((i * i != n).then_some(n / i)))
.collect();
ret.sort();
ret
}
``````

or, slightly more neatly (using a `itertools` method)

``````use itertools::Itertools; // for more convenient â€śsortedâ€ť

fn divisor(n: u64) -> Vec<u64> {
(1..)
.take_while(|i| i * i <= n)
.filter(|i| n % i == 0)
.flat_map(|i| std::iter::once(i).chain((i * i != n).then_some(n / i)))
.sorted()
.collect()
}
``````

Using `1..(1 << 32)` here and above might be a good way to fix possible overflow.

2 Likes

Yet another example

``````fn main() {
let n = 27;
let d = divisor(n);
dbg!(d);
}

fn divisor(n: i64) -> Vec<i64> {
let mut ret = (1..)
.take_while(|i| i * i <= n)
.filter(|i| n % i == 0)
.flat_map(|i| [i, n/i])
.collect::<Vec<i64>>();
ret.sort_unstable();
ret.dedup();
ret
}
``````

Playground

1 Like

If we start modifying the algorithm though â€“ admitted â€“ your modification was small, we can do a lot more, of course. E.g. sorting seems unnecessary. A good alternative would be to first store the lower divisors, then create a new `Vec` containing those plus the upper half (generated by iterating backwards).

Or we could do fancy stuff like integer factorization to increase performance (for larger numbers).

`sort_unstable` for sorting integers is a good call though.

I didnâ€™t assume you meant to improve my answer [I saw you writing; discourse gives a little indicator], and please donâ€™t feel any pressure to avoid posting a similar-looking reply written concurrently (except maybe if itâ€™s essentially completely identical); happens to me, too.

â€śmodifying the algorithmâ€ť wasnâ€™t referring to my code but to OPâ€™s algorithm

I, too, thought of roughly your approach with `dedup` which makes the `flat_map` more straightforward; but decided against modifying the algorithm because in that case, I wouldnâ€™t know where to draw the line

I didnâ€™t want to criticize your response at all, I just wanted to point out that there is a difference (in case a Rust learner wants to compare iterative and iterator-combinator approaches) and also remark that there are certainly lots of possible further algorithmic improvements over OPâ€™s code

4 Likes

Just for fun

``````fn main() {
let n = 16;
let d = divisor(n);
dbg!(d);
}

fn divisor(n: i64) -> Vec<i64> {
let mut ret = (1..)
.take_while(|i| i * i <= n)
.filter(|i| n % i == 0)
.flat_map(|i| [i, n/i])
.collect::<Vec<i64>>();

if ret.last().unwrap().pow(2) == n {
ret.pop();
}
ret.sort_unstable();
ret
}
``````

Playground

Aaaand a final one based on the suggestion by @steffahn. Although now that I think about it, it's not actually what @steffahn suggested.

``````fn main() {
let n = 16;
let d = divisor(n);
dbg!(d);
}

fn divisor(n: u64) -> Vec<u64> {
let (lower, upper): (Vec<u64>, Vec<u64>) = (1..)
.take_while(|i| i * i <= n)
.filter(|i| n % i == 0)
.map(|i| (i, n / i))
.unzip();
let last = lower.len() - 1;
let s = if lower[last] == upper[last] { 1 } else { 0 };
lower
.into_iter()
.chain(upper.into_iter().rev().skip(s))
.collect()
}
``````

Playground

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.