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
}
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.
Didn't mean to improve on your answer. I just already had it written out^^. Sorry for adding only marginal value.
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
}
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()
}
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.