(*                  PRIMI_DIV.PAS                    *)
(* Ricerca numeri primi tramite ricerca di divisori  *)
(* e ricerca dei fattori primi di un numero dato.    *)
(*                                                   *)
(* Autore: Corrado Damiano                           *)
(* Data ultima versione: 28-8-2026                   *)

program primi_div;

uses crt, dateutils, sysutils, lib_filtri, lib_listanum;

(*---------------------------------------*)
type
    p_longint = ^longint;

(*---------------------------------------*)
var
    (* oggetto gestore lista di numeri primi *)
    G_lista_primi: gestore_lista_num;
    (* gestore lista di fattori primi di un numero dato *)
    G_lista_fatt: gestore_lista_num;
    (* numero massimo di nodi inseribili in lista *)
    n_max_nodi: longint;
    (* numeri visualizzati in una singola riga *)
    numeri_riga: longint;
    (* limite per la ricerca dei primi *)
    max_ricerca: longint;
    (* esito della ricerca dei numeri primi *)
    ok_ricerca: boolean;
    (* numero di primi trovati e messi in lista *)
    n_trovati: longint;
    (* massimo numero messo in lista dei primi *)
    max_primo: longint;
    (* numero da scomporre in fattori primi *)
    num_scomp: longint;
    (* esito della scomposizione in fattori primi *)
    ok_scomponi: integer;
    (* stringa con i fattori primi trovati *)
    str_fattori_primi: string;
    (* var. per ciclo di elaborazione *)
    continua: boolean;
    (* opzione scelta dall'utente *)
    opz: byte;
    (* var. per misurare la durata dell'elaborazione *)
    t_inizio: TDateTime;
    t_fine: TDateTime;
    secondi: int64;
    minuti: int64;

(*---------------------------------------*)
(* ricerca numeri primi *)

(* cerca nella lista dei numeri primi un divisore di num *)
function cerca_div(var G_lista_p: gestore_lista_num; num: longint): boolean;
var
    trovato: boolean;
    ok: boolean;
    continua: boolean;
    num_primo: longint;
begin
    (* inizializza il puntatore al nodo corrente,      *)
    (* di cui bisogna leggere il numero contenuto;     *)
    (* all'inizio viene puntato il primo nodo in lista *)
    ok := G_lista_p.iniz_p_corrente;

    (* se la lista e' vuota, interrompe l'elaborazione *)
    if ok = false then
    begin
        cerca_div := false;
        exit; 
    end;   

    trovato := false;
    continua := true;

    while continua = true do
    begin
        (* legge il numero primo contenuto nel nodo corrente;  *)
        (* il puntatore al nodo corrente viene aggiornato      *)
        (* in modo da puntare al prossimo nodo da leggere      *)
        ok := G_lista_p.leggi_num_corrente(@num_primo);

        (* se non ha letto alcun nodo (perche' li ha gia' letti tutti)  *)
        (* interrompe il ciclo                                          *)
        if ok = false then        
        begin
            break;
        end;

        (* se il quadrato del numero primo letto e' maggiore di num,  *)
        (* e' inutile proseguire, perche' se esistesse un divisore    *)
        (* l'avrebbe gia' trovato                                     *)
        if (num_primo * num_primo) > num then
        begin
            break;
        end;

        if (num mod num_primo) = 0 then
        begin
            trovato := true;
            continua := false;
        end;
    end;

    (* ripristina il valore iniziale del puntatore  *)
    (* al nodo corrente (primo della lista)         *)
    ok := G_lista_p.iniz_p_corrente;

    cerca_div := trovato;

end;
(* fine cerca_div *)


(* mette in lista tutti i numeri primi inferiori/uguali max_ric;     *)
(* il numero di primi trovati viene assegnato a p_conta^;            *)
(* la var. booleana in uscita indica se l'elaborazione e' riuscita   *)
(* oppure no (potrebbe interrompersi anticipatamente per allocazione *)
(* non riuscita o perche' la lista e' piena)                         *)
function cerca_primi(var G_lista: gestore_lista_num; max_ric: longint; p_conta: p_longint): boolean;
var
    ok_ric_completa: boolean;
    k: longint;
    trovato: boolean;
    ok_metti: boolean;
begin
    ok_ric_completa := true;

    (* casi particolari *)
    if max_ric < 2 then
    begin
        p_conta^ := 0;
        cerca_primi := ok_ric_completa;
        exit;
    end;

    if max_ric = 2 then
    begin
        G_lista.metti_fine(2);
        p_conta^ := 1;
        cerca_primi := ok_ric_completa;
        exit;
    end;

    if max_ric = 3 then
    begin
        G_lista.metti_fine(2);
        G_lista.metti_fine(3);
        p_conta^ := 2;
        cerca_primi := ok_ric_completa;
        exit;
    end;

    (* caso generale *)
    G_lista.metti_fine(2);
    G_lista.metti_fine(3);

    p_conta^ := 2;

    k := 5;

    while k <= max_ricerca do
    begin
        trovato := cerca_div(G_lista, k);

        if trovato = false then
        begin
            ok_metti := G_lista.metti_fine(k);

            if ok_metti = true then
            begin
                inc(p_conta^);
            end
            else
            begin
                (* allocazione nuovo nodo non riuscita *)
                ok_ric_completa := false;
                break;
            end;
        end;

        inc(k, 2);
    end;

    cerca_primi := ok_ric_completa;

end;
(* fine cerca_primi *)

(*---------------------------------------*)
(* ricerca fattori primi di un numero dato *)

(* cerca nella lista dei numeri primi un divisore di num  *)
(* e lo rende in uscita; se non lo trova, esce con 0      *)
function cerca_fatt(var G_lista_p: gestore_lista_num; num: longint): longint;
var
    fatt_primo: longint;
    ok: boolean;
    continua: boolean;
    num_primo: longint;
begin
    fatt_primo := 0;

    (* inizializza il puntatore al nodo corrente,      *)
    (* di cui bisogna leggere il numero contenuto;     *)
    (* all'inizio viene puntato il primo nodo in lista *)
    ok := G_lista_p.iniz_p_corrente;

    (* se la lista e' vuota, interrompe l'elaborazione *)
    if ok = false then
    begin
        cerca_fatt := fatt_primo;
        exit; 
    end;   

    continua := true;

    while continua = true do
    begin
        (* legge il numero primo contenuto nel nodo corrente;  *)
        (* il puntatore al nodo corrente viene aggiornato      *)
        (* in modo da puntare al prossimo nodo da leggere      *)
        ok := G_lista_p.leggi_num_corrente(@num_primo);

        (* se non ha letto alcun nodo (perche' li ha gia' letti tutti)  *)
        (* interrompe il ciclo                                          *)
        if ok = false then        
        begin
            break;
        end;

        if num mod num_primo = 0 then
        begin
            fatt_primo := num_primo;
            continua := false;
        end;
    end;

    (* ripristina il valore iniziale del puntatore  *)
    (* al nodo corrente (primo della lista)         *)
    ok := G_lista_p.iniz_p_corrente;

    cerca_fatt := fatt_primo;

end;
(* fine cerca_fatt *)


(* cerca i fattori primi di num nella prima lista       *)
(* e li inserisce nella seconda;                        *)
(* l'integer in uscita puo' assumere questi valori:     *)
(* -1: scomposizione impossibile;                       *)
(* 0:  scomposizione incompleta (i fattori primi        *)
(*     potrebbero esistere, ma non si trovano           *)
(*     tutti nella lista dei primi)                     *)
(* 1:  scomposizione completa                           *)
function scomponi_num(var G_lista_p: gestore_lista_num; var G_lista_f: gestore_lista_num; num: longint): integer;
var
    continua: boolean;
    residuo: longint;
    fatt_primo: longint;
begin
    (* se la lista dei primi e' vuota, non si possono trovare fattori *)
    if G_lista_p.leggi_n_nodi = 0 then
    begin
        scomponi_num := -1;
        exit; 
    end;

    (* i numeri inferiori a 2 non hanno fattori primi *)
    if num < 2 then
    begin
        scomponi_num := -1;
        exit; 
    end;

    continua := true;

    (* all'inizio il residuo deve essere uguale al numero da scomporre;  *) 
    (* poi si ridurra', ad ogni passo del ciclo assumera' il valore      *)
    (* di residuo / fattore primo trovato                                *)
    residuo := num;

    while continua = true do
    begin
        fatt_primo := cerca_fatt(G_lista_p, residuo);

        (* se ha trovato un fattore primo... *)
        if fatt_primo > 0 then
        begin
            (*...lo mette nella lista dei fattori primi *)
            G_lista_f.metti_fine(fatt_primo);

            residuo := residuo div fatt_primo;

            (* se il residuo e' 1, significa che la scomposizione e' terminata *)
            if residuo = 1 then
            begin
                continua := false;
            end;
        end
        else
        begin
            (* non ha trovato un fattore primo *)
            continua := false;
        end;
    end;

    (* scomposizione completa *)
    if residuo = 1 then
    begin
        scomponi_num := 1;
        exit;
    end;

    (* scomposizione incompleta *)
    scomponi_num := 0;

end;
(* fine scomponi_num *)


(* dati base ed esponente, rende in uscita una stringa *)
(* che li rappresenta                                  *)
function crea_str_potenza(base: longint; esp: longint): string;
var
    s: string;
    segno_pot: string;
begin
    s := '';
    segno_pot := '^';

    if esp = 1 then
    begin
        s := IntToStr(base);
        crea_str_potenza := s;
        exit;
    end;

    s := IntToStr(base) + segno_pot + IntToStr(esp);

    crea_str_potenza := s;

end;
(* fine crea_str_potenza *)


(* rende in uscita una stringa con i fattori primi trovati;      *)
(* i fattori uguali vengono compattati aggiungendo un esponente  *)
function crea_str_fattori(var G_lista_f: gestore_lista_num): string;
var
    str_fattori: string;
    ok: boolean;
    conta: longint;
    continua: boolean;
    fattore_preced: longint;
    fattore: longint;
begin
    str_fattori := '';

    ok := G_lista_f.iniz_p_corrente;

    (* se la lista e' vuota, interrompe l'elaborazione *)
    if ok = false then
    begin
        crea_str_fattori := str_fattori;
        exit; 
    end;   

    (* lista con un solo nodo *)
    if G_lista_f.leggi_n_nodi = 1 then
    begin
        G_lista_f.leggi_num_corrente(@fattore);
        str_fattori := IntToStr(fattore);
        crea_str_fattori := str_fattori;
        G_lista_f.iniz_p_corrente;
        exit;
    end;

    (* il fattore nel primo nodo viene assegnato a fattore_preced  *)
    G_lista_f.leggi_num_corrente(@fattore_preced);

    (* contatore dei fattori consecutivi uguali *)
    conta := 1;

    continua := true;

    (* ciclo di lettura dei fattori in lista, partendo dal secondo nodo *)
    while continua = true do
    begin
        ok := G_lista_f.leggi_num_corrente(@fattore);

        if ok = true then
        begin
            if fattore <> fattore_preced then
            begin
                str_fattori := str_fattori + crea_str_potenza(fattore_preced, conta) + '  ';
                conta := 1;
            end
            else
            begin
                inc(conta);
            end;

            fattore_preced := fattore;
        end
        else
        begin
            continua := false;
        end;
    end;

    (* l'esponente da assegnare all'ultimo fattore in lista *)
    (* e' conosciuto solo dopo l'uscita dal ciclo           *)                                   
    str_fattori := str_fattori + crea_str_potenza(fattore_preced, conta) + '  ';

    crea_str_fattori := str_fattori;

end;
(* fine crea_str_fattori *)


(* data la lista dei fattori trovati, rende in uscita il relativo prodotto;  *)
(* serve per verificare la correttezza della scomposizione                   *)
function moltip_fattori(var G_lista_f: gestore_lista_num): longint;
var
    prodotto: longint;
    ok: boolean;
    continua: boolean;
    fatt_primo: longint;
begin
    (* inizializza il puntatore al nodo corrente,      *)
    (* di cui bisogna leggere il numero contenuto;     *)
    (* all'inizio viene puntato il primo nodo in lista *)
    ok := G_lista_f.iniz_p_corrente;

    (* se la lista e' vuota, interrompe l'elaborazione *)
    if ok = false then
    begin
        moltip_fattori := 0;
        exit;
    end;

    prodotto := 1;
    continua := true;

    while continua = true do
    begin

        ok := G_lista_f.leggi_num_corrente(@fatt_primo);

        if ok = true then
        begin
            prodotto := prodotto * fatt_primo;
        end
        else
        begin
            (* non ci sono piu' nodi da leggere *)
            continua := false;
        end;
    end;

    ok := G_lista_f.iniz_p_corrente;

    moltip_fattori := prodotto;

end;
(* fine moltip_fattori  *)

(*---------------------------------------*)

function menu_scelta(n_max_nodi: longint): byte;
var
    opzione: byte;
begin
    writeln('-------------------------------------------');
    writeln('RICERCA NUMERI PRIMI (max nodi ', n_max_nodi, ')');
    writeln('Cerca numeri primi.....................1');
    writeln('Mostra dati numeri primi...............2');
    writeln('Scomponi numero in fattori primi.......3');
    writeln('Uscita dal programma...................4');
    writeln;

    opzione := leggi_byte('Scegliere operazione: ');

    menu_scelta := opzione;
end;
(* fine menu_scelta *)


procedure premi_tasto;
begin
    writeln;
    writeln('Premere un tasto per continuare...');
    readkey;
end;

(*---------------------------------------*)
begin
    n_max_nodi := 10000000;
    numeri_riga := 10;

    G_lista_primi.iniz('Lista primi', n_max_nodi);
    G_lista_fatt.iniz('Lista fattori primi', n_max_nodi);

    max_ricerca := 0;
    n_trovati := 0;
    max_primo := 0;

    continua := true;

    while continua = true do
    begin
        opz := menu_scelta(n_max_nodi);

        (* creazione lista numeri primi *)
        if opz = 1 then
        begin
            G_lista_primi.svuota;

            writeln;
            max_ricerca := leggi_longint('Cercare numeri primi fino a: ');

            writeln;
            writeln('Elaborazione in corso...');

            (* memorizza il momento di inizio ricerca  *)
            t_inizio := now;

            ok_ricerca := cerca_primi(G_lista_primi, max_ricerca, @n_trovati);

            (* memorizza il momento di fine ricerca  *)
            t_fine := now;

            G_lista_primi.mostra(numeri_riga);

            if ok_ricerca = false then
            begin
                writeln;
                writeln('Elaborazione interrotta. Allocazione nodo non riuscita o lista piena');
            end;

            writeln;
            writeln('Cercati numeri primi fino a ', max_ricerca);
            writeln;
            writeln('Primi trovati: ', n_trovati);

            secondi := SecondsBetween(t_fine, t_inizio);
            minuti := secondi div 60;
            secondi := secondi mod 60;

            writeln;
            writeln('Tempo impiegato: ');
            writeln;
            writeln('Minuti: ', minuti);
            writeln;
            writeln('Secondi: ', secondi);

            premi_tasto;
        end;

        (* mostra i dati relativi a lista primi *)
        if opz = 2 then
        begin
            writeln;
            writeln('Cercati primi fino a ', max_ricerca);
            writeln;
            writeln('Numeri primi trovati: ', n_trovati);
            writeln;
            G_lista_primi.leggi_num_posiz(n_trovati, @max_primo);
            writeln('Massimo primo trovato: ', max_primo);
            premi_tasto;
        end;

        (* scomposizione di numero in fattori primi *)
        if opz = 3 then
        begin
            writeln;
            num_scomp := leggi_longint('Numero da scomporre: ');
            ok_scomponi := scomponi_num(G_lista_primi, G_lista_fatt, num_scomp);

            if ok_scomponi = (-1) then
            begin
                writeln;
                writeln('Scomposizione non effettuata');
            end;

            str_fattori_primi := crea_str_fattori(G_lista_fatt);

            writeln;
            writeln('Fattori primi: ', str_fattori_primi);

            if ok_scomponi = 0 then
            begin
                writeln;
                writeln('Scomposizione incompleta');
            end;

            writeln;
            writeln('Prodotto fattori primi trovati: ', moltip_fattori(G_lista_fatt));

            G_lista_fatt.svuota;
            premi_tasto;
        end;

        (* uscita dal programma *)
        if opz = 4 then
        begin
            continua := false;
        end;
    end;

    G_lista_primi.svuota;
    G_lista_fatt.svuota;

    writeln('-------------------------------------------');

end.
(*---------------------------------------*)
(* fine primi_div.pas *)