Follow

Con il terzo problema ci troviamo davanti la prima difficoltà, questa volta infatti il metodo più intuitivo risulta inapplicabile computazionalmente. Ma leggiamo la richiesta del problema:

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

What is the largest prime factor of the number 600851475143 ?

Dobbiamo trovare quindi il più grande fattore primo di un numero dato.

Intuitivamente ci viene da pensare che è necessario un algoritmo che trovi tutti i fattori primi di un dato numero e selezioni il più grande. In realtà possiamo trovarne uno molto più efficiente perché a noi non interessano tutti i fattori primi, ma solo il più grande.

L’algoritmo seguente fa al caso nostro:

def largestPrimeFactor(num) :
    num2 = 1.0
    prim_numbers = []
    while num2 < num:
        num2 += 1.0
        res = num/num2
        if res %2 == 1:
            num = res
            prim_numbers.append(num2)
    return prim_numbers

Num è il numero di cui vogliamo trovare il fattore primo. Num2 invece è un indice che scorre da 1 a num.

Ad ogni ciclo si confronta num e num2 e si verifica se il risultato della divisione è dispari. Se è dispari allora num diviene uguale al risultato e si aggiunge num2 alla lista prim_numbers.

L’ultimo elemento di questa lista sarà il nostro obbiettivo.

Ricalca come si vede il meccanismo usato nelle scuole quando ci veniva chiesto di scomporre in fattori primi un numero. Il concetto può riassumersi quindi in “se il numero divide lo metto in lista, se non divide provo un numero più grande”. Ovviamente con i dovuti accorgimenti.