Project Euler #3

Question:

What is the largest prime factor of the number 600851475143?

Solution:


long p3_solution(long n)
{

    long big_prime_factor = 2;
    long factor = 2;

    if (n % big_prime_factor == 0) {

        n /= big_prime_factor;

        while (n % big_prime_factor == 0)
            n /= big_prime_factor;

    }

    factor = 3;

    while ( n > 1) {

        if ((n % factor) == 0) {

            n /= factor;
            big_prime_factor = factor;

            while ((n % factor) == 0)
                n /= factor;

        }

        factor += 2;

    }

    return big_prime_factor;
}

Answer:

Con n = 600851475143 l’algoritmo ritorna big_prime_factor = 6857.

Annunci

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: