Programma Primi di un Numero

[m1ster_b1t]

Ciao a tutti vorrei chiedere un aiuto, dovrei fare un programma che memorizza i numeri primi di 50,poi legge un indice intero, suggerendo che sia minore della lunghezza dell'array, e stampa il numero primo memorizzato in quella posizione.Il programma deve continuare a funzionare anche se si decide di inizializzare la costante con una seguenza di primi piu lunga o piu corta...

Qualcuno mi potrebbe spiegare a grandi linea cosa potrei fare per fare questo programma?

[Andrea1979]

non è chiara la richiesta, ma suppongo ti sia richiesto di trovare tutti i numeri primi minori o uguali ad un certo numero dato... caricarli in un array e dare la possibilità all'utente di farsi ritornare l'n-esimo numero primo (quindi l'ennesimo elemento dell'array).

Sa molto di compiti per casa... qui di norma non se ne parla (e non si parla di norma di problematiche non inerenti a codice): dovresti quindi sviluppare qualcosa di tuo pugno ed eventualmente postare con le problematiche riscontrate nel tuo codice.

[m1ster_b1t]

Io non sono uno studente ma sto studiando il java e nelle esercitazioni mi richiede di fare questo programma, ma non mi e chiaro come faccio a dire al programma che deve solo salvarmi i numeri primi inferiori a 50

[Andrea1979]

divide et impera

- dovrai costruire una qualche routine per verificare se un numero dato è primo;
- dovrai testare tutti (non proprio, bastano solo i numeri dispari, visto che l'unico primo pari è 2) i numeri tra 2 (1 non è primo per definizione) e il tuo limite superiore;
- infilare in un array i numeri che hanno superato il test di primalità;
- prevedere un sistema di interazione con l'utente;
- gestire eventuali situazioni "anomale" (richiesto un elemento fuori dall'ordine del tuo array) o input non conformi a quanto atteso/processabile dal tuo programma.

gli ultimi due task sono a loro volta riducibili a sotto-task più piccoli.

Questa è a grandi linee la (una possibile) struttura del tuo programma. Adesso tocca a te.

[Patrick Jane]

Originariamente inviato da Andrea1979
- dovrai testare tutti (non proprio, bastano solo i numeri dispari, visto che l'unico primo pari è 2) i numeri tra 2 (1 non è primo per definizione) e il tuo limite superiore;

Se non erro è sufficiente scorrere sino alla radice quadrata del suo limite.

[Andrea1979]

Originariamente inviato da Patrick Jane
Se non erro è sufficiente scorrere sino alla radice quadrata del suo limite.

Per testare se un numero x è primo, è corretto quel che dici: basta testare tutti i numeri dispari fino alla parte intera della radice quadrata di x. Ma questo è uno dei possibili test di primalità... lì si intendeva: dovrai effettuare il test di primalità su tutti i numeri dispari minori del tuo limite (50 nel caso del nostro amico).

A dire il vero, nel caso specifico di m1ster_b1t, ovvero array etc etc, mi sembra abbastanza comodo l'applicazione del "crivello di eratostene", visto che comunque si tratta di individuare tutti i numeri primi in un certo intervallo, e non solo se un dato numero sia primo o meno. Non vorrei però mettere troppa carne al fuoco.

[Patrick Jane]

Originariamente inviato da Andrea1979
Per testare se un numero x è primo, è corretto quel che dici: basta testare tutti i numeri dispari fino alla parte intera della radice quadrata di x. Ma questo è uno dei possibili test di primalità... lì si intendeva: dovrai effettuare il test di primalità su tutti i numeri dispari minori del tuo limite (50 nel caso del nostro amico).

A dire il vero, nel caso specifico di m1ster_b1t, ovvero array etc etc, mi sembra abbastanza comodo l'applicazione del "crivello di eratostene", visto che comunque si tratta di individuare tutti i numeri primi in un certo intervallo, e non solo se un dato numero sia primo o meno. Non vorrei però mettere troppa carne al fuoco.

Si hai ragione. Oltretutto è piuttosto semplice da implementare. Poi successivamente consiglierei (dopo l'applicazione del Crivello), una ricerca binaria nel vettore (dato che dovrebbe essere ordinato, in quel caso lo si può ordinare^^).
Sarebbe un idea?

[Andrea1979]

Originariamente inviato da Patrick Jane
Si hai ragione. Oltretutto è piuttosto semplice da implementare. Poi successivamente consiglierei (dopo l'applicazione del Crivello), una ricerca binaria nel vettore (dato che dovrebbe essere ordinato, in quel caso lo si può ordinare^^).
Sarebbe un idea?

Un po' inappropriato: perché usare la ricerca binaria quando semplicemente bisogna ritornare l'i-esimo elemento di un array? Non è più semplice

return tuo_array[i];

?
La ricerca binaria è sicuramente uno strumento tra i più potenti, nel ricercare un elemento in un insieme ordinato... ma in questo specifico caso non v'è alcuna ricerca da compiere. Comunque, qui si sta mettendo ancora più carne al fuoco e di sicuro non si aiuta m1ster_b1t

[m1ster_b1t]

Non riesco solo a capire come dire al programma di prendere solo i numeri dispari....
cioe:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

[Andrea1979]

Fai una ricerca sul crivello di Eratostene di cui parlavo prima ed avrai l'illuminazione... per semplificarti le cose, parti da un array di n+1 elementi (dove n è 50 nel tuo caso specifico, ma può essere qualsiasi numero) con tutti gli interi da 0 a n nelle rispettive posizioni... ovvero:

a[0] = 0;
a[1] = 1;
a[2] = 2;
...
a[50] = 50;
...
a[n] = n;

si tratta di fare 2 cicli for, uno annidato nell'altro, ed è quanto. Niente di più, niente di meno.