Minimo fattore primo

Il minimo fattore primo di un intero è il più piccolo primo che lo divide esattamente. Per un numero primo quel fattore è il numero stesso; per un composto è il primo primo della fattorizzazione e il certificato più economico che il valore non è primo.

Cos’è il minimo fattore primo e cosa restituisce questo strumento

Ogni intero n maggiore di uno ha un multiinsieme unico di fattori primi per il teorema fondamentale dell’aritmetica, e tra quei primi c’è sempre un minimo. Quel valore si chiama minimo fattore primo, spesso abbreviato SPF nelle tabelle di teoria dei numeri e nei problemi di programmazione competitiva. Quando n è primo lo SPF è n; quando n è pari lo SPF è sempre due; quando n è prodotto di primi più grandi lo SPF è il primo primo che divide n nella prova ordinata.

Questa capacità risponde solo a quella domanda: non elenca ogni potenza prima, non calcola la funzione di Eulero e non emette certificati di primalità per interi da migliaia di bit.

Come funziona l’algoritmo di prova deterministica

Il motore controlla prima la divisibilità per due e per tre, perché i multipli pari e di tre dominano gli input quotidiani e si risolvono in tempo costante. I candidati rimanenti percorrono una ruota a sei passi della forma 6k±1 a partire da cinque, che salta ogni intero divisibile per due o tre e colpisce comunque ogni primo. Appena un candidato divide n, quel candidato viene restituito come minimo fattore primo: non serve altra ricerca perché i candidati sono provati in ordine crescente.

Se il ciclo raggiunge la radice quadrata intera di n senza trovare un divisore, n deve essere primo e viene restituito come proprio minimo fattore primo. Tutta l’aritmetica usa BigInt internamente entro l’intervallo di intero sicuro pubblicato così i prodotti intermedi restano esatti; poi i risultati sono serializzati come numeri JavaScript ordinari nella risposta.

Dove un calcolatore del minimo fattore primo si inserisce nei flussi reali

Studenti e docenti usano un calcolatore del minimo fattore primo per verificare compiti, mostrare perché un numero fallisce un’affermazione di primalità nominando il primo primo ostruttivo e costruire intuizione prima della fattorizzazione completa. Gli sviluppatori di applicazioni lo chiamano quando una pipeline serve solo il minimo fattore — ad esempio per togliere la parità, per una prova in stile Pollard prima di metodi più pesanti, o per rifiutare valori di configurazione palesemente composti con un primo concreto anziché un semplice false.

Gli ingegneri dei dati filtrano colonne numeriche che dovrebbero avere forma di primo: qualsiasi valore il cui SPF sia minore del valore stesso è composto, e il fattore finisce nel registro di audit senza espandere l’elenco completo dei fattori. Preferisca questo strumento quando l’intento di ricerca è strettamente «qual è il minimo fattore primo di n?», non quando serve ogni potenza prima, certificati di primalità per enormi interi multiprecisione o test probabilistici con liste di testimoni personalizzate.