[Rust] Optimizing code

tobot

[Rust] Optimizing code [Copy link]

I was sent a very basic question this morning, and I tried to do it, but found it unsuccessful.

https://bbs.eeworld.com.cn/thread-1283777-1-1.html

Except for the large amount of data, everything else is relatively easy. I discussed with my friends this morning and found two main directions for improvement:

About f(n):

First, create a prime number array. For a given value of n, only take the first k items less than n, compare them in reverse order, and exit if they are its factors, and quickly obtain the largest prime factor.

About h(n):

We know that h(x) is a non-monotonic increasing sequence, which is the largest g(x) when x∈[2,n]. g(x) is the sum of several items, so there is no need to calculate every number less than n. When g(n) is calculated when x=n, if f(n+9)<f(n), then g(n+1)=g(n), otherwise h(n+1) is calculated and compared with g(n), and the larger value is taken as the value of h(n+1).