Eccoci.

Largest Prime Factor

ℹ️Published on Friday, 2nd November 2001, 06:00 pm; Solved by 588084;
Difficulty rating: 5%

Problem 3

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

What is the largest prime factor of the number $600851475143$?

Soluzione

Qui propongo tre metodi: il primo one-liner sfruttando le potenzialità offerte da Julia (moralmente, la libreria Primes); il secondo usando il primo metodo che (credo) verrebbe in mente, ma risulta molto costoso, inefficiente; il terzo una versione sempre a mano ma più ottimizzato e ragionato.

n_test = 131956268 # giusto un numero di test

131956268

Metodo one-liner: usando le potenzialità di Julia.

using Primes
@time maximum(keys(factor(n_test)))

  0.381594 seconds (432.37 k allocations: 22.839 MiB, 99.97% compilation time)
82267

Metodo naive (il primo che verrebbe in mente): scorriamo dal più alto candidato fattore primo (ovvero \(n/2\)) a scendere, e ci fermiamo appena troviamo il primo, dato che stiamo scorrendo verso il basso e quindi il primo che incontriamo sarà di certo quello massimo.

function find_max_pfactor_naive(n)
	lim_initial = div(n,2)
	for i in lim_initial:-1:1
		if isprime(i) && n%i == 0
			@show i
			break
		end
	end
end
@time find_max_pfactor_naive(n_test)

i = 82267
  4.298030 seconds (5.85 k allocations: 301.367 KiB, 0.21% compilation time)

Metodo efficiente: scorriamo sui numeri \(i\) da 2 a salire, e se questi dividono il numero target \(n\) allora trasformiamo \(n\) come \(n/i\) per tutte le volte possibili, ovvero finché non esauriamo l'esponente di quel fattore primo \(i\). Quando \(n\) sarà diventato uguale a 1 vorrà dire che avremo trovato il fattore primo più grande, dato che sarà l'ultimo per cui potremo dividere \(n\). Questo metodo è efficiente perché, a differenza del precedente, si evita il controllo sulla primalità del fattore \(i\) (in questa funzione infatti manca il controllo isprime(i) che invece c'era prima) grazie al fatto di eseguire il loop sui numeri stavolta in ordine crescente.

function find_max_pfactor_fast(n)
	i = 1
	while n != 1
		i += 1
		if n % i == 0
			println("n = $(rpad(Int64(n),20)) -> $i è un fattore primo di n")
			while n % i == 0
				n = n/i
			end
		end
	end
	println("n = $(rpad(Int64(n),20)) -> finito!")
	println("=> $i è il più alto fattore primo di n")
end
@time find_max_pfactor_fast(n_test)

n = 131956268            -> 2 è un fattore primo di n
n = 32989067             -> 401 è un fattore primo di n
n = 82267                -> 82267 è un fattore primo di n
n = 1                    -> finito!
=> 82267 è il più alto fattore primo di n
  0.042109 seconds (55.63 k allocations: 2.814 MiB, 98.57% compilation time)

E quindi la vera soluzione è

@time find_max_pfactor_fast(600851475143)

n = 600851475143         -> 71 è un fattore primo di n
n = 8462696833           -> 839 è un fattore primo di n
n = 10086647             -> 1471 è un fattore primo di n
n = 6857                 -> 6857 è un fattore primo di n
n = 1                    -> finito!
=> 6857 è il più alto fattore primo di n
  0.000087 seconds (55 allocations: 2.008 KiB)