Smooth numbers are used in cryptography to provide fast factorization methods. A smooth number is defined as a number whose factors are smaller than a given value. For a 5-smooth number, the factors must be equal to five or less. Every value, apart from prime numbers can be reduced to the multiplication of prime numbers. For example 102 is equal to 2 x 3 x 17 [here]. A value of 56 is 2 x 2 x 2 x 7, and is thus 7-smooth, but not 3-smooth nor 5-smooth. In the following we determine the smooth numbers up to 1,000:
Smooth Numbers with Rust |
Method
Smooth numbers are used in cryptography to provide fast factorization methods. A smooth number is defined as a number whose factors are smaller than a given value. For a 5-smooth number, the factors must be equal to five or less. Every value, apart from prime numbers can be reduced to the multiplication of prime numbers. For example 102 is equal to 2 x 3 x 17 [here]. A value of 56 is 2 x 2 x 2 x 7, and is thus 7-smooth, but not 3-smooth nor 5-smooth.
For 3-smooth we will not have any factors who have prime numbers greater than 3 as factors:
[1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96, 108, 128, 144, 162, 192, 216, 243, 256, 288, 324, 384, 432, 486, 512, 576, 648, 729, 768, 864, 972]
A value of 28, for example has factors of 2×2×7 (where the largest factor is 7), and will thus not be 3-smooth, but 16 will, as it has factors of 2×2×2×2 (where the largest factor is 2).
The following outlines some sample code:
use std::cmp; use std::env; fn findMaxPrimeDivisor(mut n: i32)->i32 { let mut max_prime_div= 1; if n == 1 { return 1; } while n % 2 == 0 { max_prime_div= 2; n = n / 2; } let size = (f32::powf(n as f32,0.5) as i32) + 1; for odd in (3..size).step_by(2) { while n % odd == 0 { max_prime_div= odd; n = n/ odd; } } max_prime_div= cmp::max (n, max_prime_div); max_prime_div } fn generate_p_smooth(p: i32, end: i32) ->Vec{ let mut intvec: Vec = Vec::new(); intvec.push(1); for i in 2.. (end + 1) { if findMaxPrimeDivisor(i) <= p { intvec.push(i); } } return(intvec); } fn main() { let mut vals: Vec = Vec::new(); let mut p=3; let mut end=1000; let args: Vec = env::args().collect(); if args.len() >1 { p = args[1].parse().unwrap();} if args.len() >2 { end = args[2].parse().unwrap();} println!("{}-smooth, end={}",p,end); vals = generate_p_smooth(p, end) ; println!("{:?}",vals); }
One area of Python I really do not like it the usage of the loop() in the for statement. It really doesn't make any sense for me. In Rust there is a nice simple format. For a loop for i equal to 1 to 10 is:
for i in (1..10){ }
But, how do we increment the value in the loop with a value greater than 1? Well, we have a step_by() modifier. For example, to start at 3 and go up to size, in steps of 2:
for odd in (3..size).step_by(2) {
The definition of functions makes complete sense to me, too. In the following we pass a value of n (which is a 32-bit integer) into the function. We make it mutable, so that we can change it in the function. Then we define the output value (which is a 32-bit integer):
fn findMaxPrimeDivisor(mut n: i32)->i32 {
The way Python can grow arrays is also a little confusion. In Rust, cannot let them grow as they keep their dimensions thoughout the program. To grow a data array, we use a Vector in Rust, and the push() method to add a value onto the end of the vector:
for i in 2.. (end + 1) { if findMaxPrimeDivisor(i) <= p { intvec.push(i); }
To remove an element, we can use the pop() method. Rust, too, has a wide range of maths functions. In this case we use a power function using floating point values:
let size = (f32::powf(n as f32,0.5) as i32) + 1;
As we see, Rust is very much focused on data types, and where we formalise the data types we use at any given time. Notice how we use "as f32" to convert an integer to a 32-bit floating point value. If you are interested, here's the running code: