Project Euler Question 3

Goal: To begin the journey of becoming a World Authority in Record Keeping and Error Correction

Development Log | Project Euler Question 3

In order to properly learn a language exposure and real projects are important. Those pain points where you're not sure how X or Y works and learning in a sort of trial by fire is helpful. In this case nothing was ACTUALLY on fire. Nor was this some critical code that needed to be repaired otherwise many lives could be lost.

It was Project Euler Question 3. At first I was trying to brute force it, but because of the 1 minute timeout they suggest, I knew that I was doing it wrong. Next I tried to sorta do something with bloom filters to try and make it go faster? But it didn't really work and it was a half baked idea on hashmaps and skiplists all in order to drive down the search time from something from n² to less then that by a substancial factor. Eventually I reached what I believe is sqrt(n)*n for when N is large? But this doesn't account for how large primes or primes spacing out is. Because I employed an early termination condition in the inner loop check (see below).

What also took so long on this was the fact that I misunderstood the assignement at first. Which was very disheartening.

However I came up with a rough big O of sqrt(N)*N.

///
/// <p>The prime factors of $13195$ are $5, 7, 13$ and $29$.</p>
/// <p>What is the largest prime factor of the number $600851475143$?</p>
/// What is the largest prime factor of the number?
///
/// Total Time: 70
/// Right now trying a few tricks to speed up the process:
///     1) searching in reverse order from large_number.sqrt() from top down
///     2) caching largest prime top make internal searching or checking alot faster
///     3) Using bloom filter but I think I didn't actually use it?!
/// Completed on July 30th 2025 6857 is the answer.
fn euler_p3() {
    let search_number:i64 = 600851475143;
    let mut current_number:i64 = 1;
    let mut largest_found_prime:i64 = 2;

    let upper_search_bound:i64 = search_number.isqrt();

    for i in (3..upper_search_bound).rev() {
        if search_number % i == 0 {
            let mut is_prime = true;
            for jj in largest_found_prime..i {
                if i % jj == 0 {
                    is_prime = false;
                    break;
                }
            }
            if is_prime {
                current_number = i;
                largest_found_prime = i;
            }
        }
        if (largest_found_prime > 2) {
            break;
        }
    }
    println!("Largest prime found {current_number}");
    // Prime factorization is taking the smallest prime, factorizing it out, then repeating till you have no other numbers.

    // Start from 2 and work up
    // We will check if the number factors into the current number cleanly
    // Keep doing till the latest number is only a prime
    // Return latest entry as largest


}

I left in the comment that was me first understanding prime factorization. Just because I finished the problem and I wanted to leave in a momento of where I started.

#rust #projecteuler #bigOnotation

Side note, I wanted to put it into DeepSeek and it took 267 seconds to think before it came up with an answer which looks correct. Also as it pointed out and I took the gamble on was size of largest prime factor, relative to number. But it paid off! So I was playing fast and loose with primes... Anyway if you're all the way down here the prime number was 6857.