Fattori primi

[Gas75]

Salve, mi sto cimentando nella scrittura del classico algoritmo per determinare i fattori primi di un intero, sfruttando un programmino scritto una vita fa su una calcolatrice Sharp che aveva un linguaggio tutto suo (ma che padroneggiavo) e cercando di tradurlo in Java, inserendo il necessario per acquisire dati di input e gestire le eventuali eccezioni...

Sono approdato a questo...

import java.io.InputStreamReader;
import java.io.BufferedReader ;
import java.io.IOException;
import java.util.ArrayList;


public class FattoriPrimi {
    
    public static void main(String args[]) {
        
        InputStreamReader numero = new InputStreamReader(System.in);
        BufferedReader myInput = new BufferedReader (numero);
        String stringa = new String();
        int intero = 0;
        ArrayList<Integer> fattori = new ArrayList<Integer>();
        int i;
        
        try {
            System.out.print("Inserisci un numero di cui determinare i fattori primi: ");
            stringa = myInput.readLine();
            intero = Integer.parseInt(stringa);
            i = intero;
            
            for (int d = 2; d < intero; d++) {
                if (intero%d == 0) {
                    fattori.add(d);
                    intero = intero/d;
                }
            
            }
            System.out.println("Il numero " + i + " e' divisibile per " + fattori);
        }
        catch (IOException ioe) {
            System.out.println("Si e' verificato un errore: " + ioe);
            System.exit(-1);
        }
        catch (Exception e) {
            System.out.println("Il numero immesso non e' un intero!");
        }
        
    }
    
}

Dopo essere andato abbastanza spedito nella scrittura del codice, mi sono bloccato notando alcune imperfezioni dato che vorrei visualizzasse (a differenza della versione per calcolatrice) ogni fattore primo soltanto una volta, e che li visualizzasse tutti, invece se gli passo 26 mi visualizza soltanto [2] (senza il 13), così come se gli passo 65 visualizza soltanto [5]. Se però gli passo 100, visualizza [2, 5] correttamente.
Fuori dal for potrei inserire un add(intero), e così facendo visualizzerei [2, 13] per il 26 ma anche [2, 5, 10] per il 100.
Se poi gli passo 2016, mostra come fattore primo anche il 4!

Devo usare un altro for annidato?

[Ansharja]

Per risolvere il primo problema basterebbe inserire il "<=" come condizione del for altrimenti, prendendo ad esempio il 26, dopo aver diviso per 2 intero varrà 13, ma il ciclo termina con d = 12.


Per evitare di inserire divisori che sono multipli di altri divisori mi sembra che un while annidato possa essere una buona soluzione: prima di passare all'iterazione successiva, incrementando d, continui a dividere intero per d fino a quando il resto della divisione è 0, facendo attenzione a non inserire il fattore più volte nella lista.

[Gas75]

Col <= mi include anche 10 se cerco i fattori primi di 100. Credo col while che dici si possa risolvere. Grazie.

[Ansharja]

Col <= mi include anche 10 se cerco i fattori primi di 100

Sì certo, il "<=" serve solo per evitare di non considerare qualche divisore, per risolvere l'altro problema serve qualcos'altro, un ciclo interno è una possibile soluzione, magari ce ne sono altre.
Ma sono due problemi diversi, il while interno non ti consente di ottenere 13 come divisore di 26, come nel tuo esempio, ti fermi comunque prima.

[Gas75]

Ho risolto. Questo è il blocco interessato...

			for (int d = 2; d <= intero; d++) {
				if (intero%d == 0) {
					fattori.add(d);
					intero = intero/d;
					while (intero%d == 0)
						intero = intero/d;
				}
				
			}

Ho anche risparmiato una String, passando come argomento del parseInt direttamente myInput.readLine()

[schumy2000]

Nel for che utilizzi
for (int d = 2; d <= intero; d++)
potresti anche utilizzare intero/2.
Ad esempio se stai provando 50, è inutile che vai a testare il resto per numeri maggiori di 25 perché il test (il tuo if) fallirà sempre.
In questo modo computazionalmente è più leggero.

Ciao.

[Gas75]

intero/2 come controllo boolean nel for pare non funzionare perché se immetto 26 non mi dà 13 come fattore primo.
Diventa comunque intero/d ogni volta che trova un fattore primo: se immetto 50 ho
d = 2 --> intero/d = 25
d = 3 --> intero = 25
d = 4 --> intero = 25
d = 5 --> intero/d = 5
ed esce dal for.