Esercizio con true false

[MPG]

:brindiamo:

 

[petrusic]

Io non so quale segmento numerico ti interessa, ma, banalmente, io farei una tabellina di numeri primi (almeno fino a 3 cifre) e ricercherei il numero dentro tale tabellina, mentre per i numeri con più di 3 cifre penserei ad un calcolo matematico mirato.
Non so dirti di più perchè ho perso lo smalto matematico dell'età giovanile, però, in mezzo alla polvere virtuale, ho trovato questo

 

[BAT]

Una precisazione: i divisori dispari (fino al limite della radice quadrata) sono solo quelli primi, gli altri infatti sono già multipli di un numero primo (è lo stesso motivo per cui si eliminano tutti i numeri pari).. perché, proprio con la fattorializzazione, trovi i valori primi che formano un numero.

Quindi, nel caso di 101 le divisioni da verificare sono per 3, 5 e 7, il 9 non serve perché hai già fatto per 3 (se è multiplo di 9, a maggior ragione sarà multiplo di 3!), così come per 100 ( che essendi pari non verrebbe nemmeno consideranto) sono state eliminate a priori (visto che si considerano solo numeri primi) le divisioni verificate per 2, 4, 10 (6 e 8 non lo sono)..

Considerando solo i numeri primi fino alla soglia della radice del numero, le divisioni da effettuare diminuiscono notevolmente nel caso di numeri grandi, quindi la velocità.

Pur concordando con le tue osservazioni, ti faccio notare che l'approccio che tu proponi presuppone che tu abbia a disposizione una lista/database/elenco/quel-che-ti-pare di numeri primi: le cose però non stanno così. Limitandosi a interi unsigned a 32 bit ci sono 203.280.220 numeri primi inferiori a 2^32-1; ciascuno di essi occupa 4 byte, tutti insieme occupano qualcosa più di 775 MiB su un ipotetico database di numeri primi (peraltro limitato). Il meglio che si può fare è limitarsi alla radice quadrata del massimo numero rappresentabile, in tal caso la lista si riduce a soli 6542 numeri primi (meno di 26 KiB), cioè al peggio a 6542 divisioni.
Questo è l'unico modo di limitare al massimo le divisioni su un algoritmo di ricerca esaustiva e solo presupponendo di limitarsi a interi a 32 bit (se allarghi l'intervallo devi allungare la lista).

Invece, il calcolo di radice quadrate o peggio cubiche è eccessivamente oneroso dal punto di vista del calcolo, mentre gli altri metodi che citi non sono applicabili in modo efficiente: si d'accordo, è ovvio che se un numero non è divisibile per 3 allora non è divisibile per nessun multiplo di 3, così come non è divisibile per i mutlipli di qualsiasi altro numero primo inferiore alla radice del numero che controlli, ma questo non ti porta a nulla di nuovo: ogni volta che devi controllare un possibile nuovo divisore dovresti prima "capire" se per caso non è un multiplo di un numero primo precedentemente testato come divisiore, ed è un approccio sbagliato: o hai già una lista di primi pronta (e lunga) oppure i numeri primi precedenti te li devi ricordare (il che implica che la lista dei primi te la devi costruire).
In alternativa dovresti implementare un crivello e scovare i primi fino alla radice quadrata, una volta che li hai trovati dividere solo per essi...
In definitiva, l'unico modo reale di limitare le divisioni è avere una lista di primi già precostruita ed eviti pure il crivello.

Però concettualmente è errato perché dal punto di vista teorico non risolve il problema generale.
Inoltre l'esercizio non presuppone l'esistenza di nessuna lista/database di numeri.
Usando le divisioni non è possibile migliorare l'algoritmo di controllo, serve una conoscenza più avanzata di aritmetica modulare e/o teoria dei numeri.

 

[Andretti60]

Scusate ragazzi, ma così mi spaventate e confondete l'autore della discussione, che è alle prime armi è deve solo risolvere un esercizio scolastico e non andare sulla luna :)
Restate in tema per favore.

 

[BAT]

sono d'accordo con te: il check di primalità è un esercizio base che viene dato per esercitarsi su cicli e ritorno di valori di verità, altre sofisticazioni, pur se ben accette, a questo livello non sono richieste (anzi, a volte sono fuorvianti come questa discussione sta dimostrando...)

 

[1nd33d]

sono d'accordo con te: il check di primalità è un esercizio base che viene dato per esercitarsi su cicli e ritorno di valori di verità, altre sofisticazioni, pur se ben accette, a questo livello non sono richieste (anzi, a volte sono fuorvianti come questa discussione sta dimostrando...)

Vero, in questi casi penso che sia meglio non cercare di costruire soluzioni più complesse della più semplice e intuitiva, che deriva dalla definizione stessa di numero primo, ovvero il fatto di non essere divisibile per nessun numero intero ad accezione di 1 e se stesso.
Da come è iniziato il thread (e dal primo codice proposto dall'utente), all'utente suggerirei, in queste fasi iniziali, prima ancora di mettere mano al codice, di scriversi su un foglio di carta l'idea risolutiva in forma di pseudocodice, e poi, solo poi, tradurre in linguaggio di programmazione.

 

[rctimelines]

Pur concordando con le tue osservazioni, ti faccio notare che l'approccio che tu proponi presuppone che tu abbia a disposizione una lista/database/elenco/quel-che-ti-pare di numeri primi: le cose però non stanno così. Limitandosi a interi unsigned a 32 bit ci sono 203.280.220 numeri primi inferiori a 2^32-1; ciascuno di essi occupa 4 byte, tutti insieme occupano qualcosa più di 775 MiB su un ipotetico database di numeri primi (peraltro limitato). Il meglio che si può fare è limitarsi alla radice quadrata del massimo numero rappresentabile, in tal caso la lista si riduce a soli 6542 numeri primi (meno di 26 KiB), cioè al peggio a 6542 divisioni.
Questo è l'unico modo di limitare al massimo le divisioni su un algoritmo di ricerca esaustiva e solo presupponendo di limitarsi a interi a 32 bit (se allarghi l'intervallo devi allungare la lista).

Invece, il calcolo di radice quadrate o peggio cubiche è eccessivamente oneroso dal punto di vista del calcolo, mentre gli altri metodi che citi non sono applicabili in modo efficiente: si d'accordo, è ovvio che se un numero non è divisibile per 3 allora non è divisibile per nessun multiplo di 3, così come non è divisibile per i mutlipli di qualsiasi altro numero primo inferiore alla radice del numero che controlli, ma questo non ti porta a nulla di nuovo: ogni volta che devi controllare un possibile nuovo divisore dovresti prima "capire" se per caso non è un multiplo di un numero primo precedentemente testato come divisiore, ed è un approccio sbagliato: o hai già una lista di primi pronta (e lunga) oppure i numeri primi precedenti te li devi ricordare (il che implica che la lista te la devi costruire).
In alternativa dovresti implementare un crivello e scovare i primi fino alla radice quadrata, una volta che li hai trovati dividere solo per essi...
In definitiva, l'unico modo reale di limitare le divisioni è avere una lista di primi già precostruita ed eviti pure il crivello.

Però concettualmente è errato perché dal punto di vista teorico non risolve il problema generale.
Inoltre l'esercizio non presuppone l'esistenza di nessuna lista/database di numeri.
Usando le divisioni non è possibile migliorare l'algoritmo di controllo, serve una consocenza più avanzata di aritmetica modulare e/o teoria dei numeri.

Ho solo detto di

1) ridurre il range di numeri su cui cercare escludendo i pari, i quadrati e i cubi.
2) costruire progressivamente un vettore di numeri primi che saranno quelli usati per le divisioni di verifica evitando di dover dividere per numeri dispari inutili (ovviamente non può essere precostituito altrimenti sarebbe una contraddizione)

Le radici cubiche le avevo messe in dubbio pure io, anche se però fai una precompilazione della lista di ricerca potresti risparmiare tempo dopo.


Inviato dal mio Nexus 5 utilizzando Tapatalk

 

[rctimelines]

Vero, in questi casi penso che sia meglio non cercare di costruire soluzioni più complesse della più semplice e intuitiva, che deriva dalla definizione stessa di numero primo, ovvero il fatto di non essere divisibile per nessun numero intero ad accezione di 1 e se stesso.
Da come è iniziato il thread (e dal primo codice proposto dall'utente), all'utente suggerirei, in queste fasi iniziali, prima ancora di mettere mano al codice, di scriversi su un foglio di carta l'idea risolutiva in forma di pseudocodice, e poi, solo poi, tradurre in linguaggio di programmazione.

Ma infatti, è quello che ho detto pure io all'utente: parti dalla definizione teorica e implementala correttamente.
In seconda battuta, come poi è emerso che glielo ha chiesto pure il prof, vedi di trovare Delle ottimizzazioni.

Tra l'altro inutile spingersi con questo sistema alla ricerca di numeri primi al limite delle capacità di calcolo del PC, in tal caso esistono metodi statistici con i logaritmi basati sulle teorie di Gauss.

Inviato dal mio Nexus 5 utilizzando Tapatalk

 

[petrusic]

Trattandosi di un esercizio da apprendimento, io che indosso pure la tuta di apprendista, modificherei l'esercizio limitando la digiatzione ad un numero di non più di 3 cifre e scorrerei, come detto prima, un semplice array monodimensionale composto di soli numeri primi.
Se l'array è però un argomento ancora prossimo, sfrutterei allora i criteri di divisibilità.
Lascerei perciò il mondo dell'infinito relativo ai numeri ed ai numeri primi ad eventuali necessità future.

 

[BAT]

Non va bene per gli stessi motivi già detti: la lista di primi non la devi creare né la devi avere. Questo è un esercizio da risolvere con un banalissimo while.
Per numeri "piccoli" (e a 32 bit sono sufficientemente piccoli) il controllo termina rapidamente anche con una ricerca "ben fatta" (escludere tutti i pari tranne il 2, controllare solo divisori dispari fino al più alla radice quadrata intera del n. da controllare, e amen se si fanno tante divisioni inutili).

 

[Mursey]

modificherei l'esercizio limitando la digiatzione ad un numero di non più di 3 cifre e scorrerei, come detto prima, un semplice array monodimensionale composto di soli numeri primi.

Se fossi l'insegnate non ti darei la sufficienza con una soluzione del genere :P

 

[petrusic]

Se fossi l'insegnate non ti darei la sufficienza con una soluzione del genere :P

Ma come ti permetti? Da quale cattreda pensi di potere manifestare una simile arroganza?

 

[Blume.]

Ma come ti permetti? Da quale cattreda pensi di potere manifestare una simile arroganza?

Se non ci fosse una emoticon potrei anche darti ragione, mi pare invece che il tono voglia essere gioviale, mi riferisco alla tua segnalazione.

 

[petrusic]

Se non ci fosse una emoticon potrei anche darti ragione, mi pare invece che il tono voglia essere gioviale, mi riferisco alla tua segnalazione.

Mi dispiace, ma non sono d'accordo. E non sono d'accordo perchè certi toni, detti in tono scherzoso, sono frequenti e permessi fra vecchi amici.
Ripeto quanto espresso nella segnalazione: mi ritengo indignato ed offeso.

 

[Mursey]

Mi dispiace, ma non sono d'accordo. E non sono d'accordo perchè certi toni, detti in tono scherzoso, sono frequenti e permessi fra vecchi amici.
Ripeto quanto espresso nella segnalazione: mi ritengo indignato ed offeso.

Mi dispiace di averti offeso, non era mia intenzione.

Tuttavia la soluzione da te proposta non è un buon esempio per chi vuole imparare a risolvere problemi con la programmazione.
Poi liberi tutti di fare quello che si vuole, è solo il mio parere.

PS: lavoro da 20 anni come programmatore nella divisione 'ricerca e sviluppo' di una multinazionale.