Project Euler - Rust Problem 3

 Project Euler

Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Ok...  this is basically a question asking two questions.

First Question

What are all the factors of a given number?

I realize that it's asking specifically about 600,851,475,143.  However, when looking at these problems, it's best to start with the abstract and assume that at any given time, you'll be given a different input.  The reason for this is sometimes you will.  Not to mention it's great to approach it this way, allows you to get used to thinking in ways that takes the unknown into account.

So, how do we find the factors of a given number? And before we start, what is a factor?

A factor is defined as...

any number that can be multiplied by another to get the original number.  

For instance, factors of 4 are 1,2,4.  1*4 = 4, 2*2 = 4.  We won't deal with the negative numbers and fractions are never a factor.

So how do we find these numbers?

The brute force method is to loop through all the numbers 1 to the given number and divide the given number by them. If they divide evenly, they are a factor.  Add those to a Vec.  Test them all to filter out all the prime ones and return the largest. 

You could also loop through, divide evenly, test if prime, add prime to the vec and take the largest.

This is a perfectly valid and extremely long way to do this.

NOTE: Prime numbers are numbers that are evenly divisible by 1 and themselves and that is it.

another way would be to loop through the numbers 1 to N and test if they're prime first and then see if they're a factor.  You could also take a list of known prime numbers and start there.

Determining a prime number is first asking is it odd? Even number can't, by definition be prime outside of the number 2.  So you're Even? You're out... (sad face).  So it's odd.  Now start dividing that number by all numbers less than half of that number rounded down.  If you get an evenly dividable number (aka N%x == 0) then it's not prime.

How many factors does the number have?

In the process of finding all the prime numbers. We can locate the number of factors, which could help.

Using the following formulas.

Take the given number and the first 3 prime factors and the number of them as powers

N = Xa × Yb × Zc

40 would be 40 = 2 * 20.  20 isn't prime so we factor that further. 40 = 2 * (10 * 2). 10 isn't prime. 40 = 2 * 2 * 2 * 5. or N = 2^3 * 5^1 * 1^1

Total number of factors can be calculated using

N = (a+1)(b+1)(c+1)  

In the case of 40 there are 4 factors. 3+1*1+1*1+1

4*2*2 = 16... well not quite

we remove the factor of c because of the 1 to the 1st power.  but that leaves 8. we can see that there are only 4 elements.  Three of the 2 and one 5. 

well, we're forgetting the negatives.  So you divide by 2. That leaves 4 factors which is what we have.

Irrelevant 

Now this is great info to have.  However, it doesn't help us here.  I will tell you that the given number here has 4 prime factors.  That means it comes out to 1+1 * 1+1 * 1+1 or 8 then divide by 2 for the negative numbers.  That number was specifically picked as it has only 4 factors and all of them are prime.  This method could be used to check the answer to make sure that all cases have been found.  However, the first prime in this case is the 20th prime number 71.  So this strategy for this problem doesn't really help us.

So how will we approach this?

NOTE: I did find after I solved this that some people use a math principal called the Sieve of Eratosthenes   I was unaware this existed but it's an interesting read.

Rust has a crate for that.

primes

once we use the crate, we can then iterate through all the prime factors of a number.

use primes;

fn main() { 

     println!("{:?}", primes::factors(600851475143)); 

}

Boom. We have a return with 4 values.

we can even make a function to accept any value.

use primes;

fn main(){

pr_fac(600851475143)

}

fn pr_fac(x: u64){

println!("{:?}", primes::factors(x));

}

That works. 

We can go on.  Basically, what I learned from this is you don't have to reinvent the wheel.  We all have built on the people before us.  We extend their work.  While I can certainly make a brute force function that finds all the primes and loops through and ... Yeah that's how I approached it with python.

Nope, there's an app for that, there's a crate for that.  That isn't to say this is the best way.  I realize, it's kind of cheap and a little lazy.  Shrug.

EDIT: Btw if you just want the largest change the following

println!("{:?}", primes::factors(x));

to...

println!("{:?}", primes::factors(x).pop());

will return the last value in the Vec

Second EDIT: it comes after EDIT but before third edits...

so I forgot to look through and go over the answers in Rust that were posted before.

Most of them are as I described the brute force approach above.  They work just fine and there's no issue.  I also didn't time mine cause rust playground isn't fun and I know I could do it on my computer but I like there's as a common benchmark among all the answers on here. so... yeah

Other Users Responses

User davxy submitted this yesterday 1/2/21

const NUM: u64 = 600851475143;

fn main() {

    let mut val = NUM;

    // Fast div by two

    while val & 1 == 0 {

        val >>= 1;

    }

    let mut i = 3;

    while val != 1 {

        if val % i == 0 {

            val /= i;

        } else {

            i += 2;

        }

    }

    println!("{}", i);

}

NOTE: Writing this after evaluating this code. davxy knows a thing or two... just saying.

Not sure what's going on here at a glance. I'll start at the top.

He declares the constant NUM as the number in question. He then assigns the value of the constant to a variable he's made mutable. 

Next he "fast divide by two" --

while val & 1 == 0 do this thing... val >>=1

So I looked up val >>= 1 and it references variable >>= expression right-shift and assignment.

I've never seen this before.  According to stack overflow, left shift by 1 is equal to multiplying by base 2.  Right shift by 1 is equal to dividing by base 2.  So val >>= 1 is the same as val = val >> 1 which is the same as val / (2^1).   

the example they give is pretty neat. Basically, you take the binary value of a number say 16.  16 in binary is 10000.  or 1 in the 16th's place.  if you shift it to the right (divide) you pull it down to 1000 or 1 in the 8th's place.  You've divided it by 2.  That's what's going on here.  I didn't even know that was an option. That's awesome.

Back to the val & 1 == 0 thing.  It says it could be a few things but in this context looks like a bitwise AND.  Under bitwise opporators, it explains it as it performs a boolean and operation on each of the arguments.  So a & b will resolve true/false and then... operation? and then that is evaluated again against 0 which resolves to another boolean.

According to the wiki on bitwise opps, the & bitwise compares both equal length numbers in biary and compares the corresponding values to each other.

    0101 (decimal 5)
AND 0011 (decimal 3)
  = 0001 (decimal 1)

Each bit is multiplied together.  in this case 0 and 0 in the 8th's place resolve to 0.  the 1 (in decimal 5) multiplies by the 0 (in decimal 3), both in the 4's place, resolving to 0.  The 0 (in decimal 5) multiplies by 1 (in decimal 3), in the 2's place, resolving to 0.  Finally, the 1's (in both decimal 5 and 3) in the one's place resolve to 1.  So the bitwise AND value of 5 and 3 is 1.

Bring that back to our current discussion.

val & 1 == 0

val in binary is 

1000101111100101100010011110101011000111  ... and the binary value of 1 at equal length is 

000000000000000000000000000000000000001

So what this is saying is that while val & 1, in binary form, resolve the bitwise and function and resolve to 0, move the bits over to the right by 1, effectively dividing the whole number by 2.

This is interesting that he did this because it means he added it knowing that it needed to be a first step logically even though the given number resolves to 1 and never runs the while.

 The rest of this runs off the principal of the odd numbers can only be prime after 2. 

So there's a variable i that = 3.  if the val does not equal 1 then evaluate the bool for val divided by i has no remainder.  if it does then divide val by i.  if not then add 2 to i and repeat.  once you've reduced val to 1, you know have an i value equal to the largest prime number that is a factor of the given number.

Looking through the entries, there's another one but it's basic brute force and it's huge.

That's it.  Learned a lot, not by doing this but by looking through davxy's code.  It's really important to both share your code and read others to learn from it.