Esercizio con true false

[rctimelines]

Ho spiegato sopra come si fa, esistono solo metodi che voi chiamate "brute Force", solo che possono essere ottimizzati.
Bisogna dividere il numero per tutti i precedenti finché non trovi una divisione senza resto. La caratteristica dei numeri primi è che sono infiniti e non hanno alcuna regolarità di distribuzione, di conseguenza non esiste una formula per individuarli (la loro forza) ma bisogna cercarli ad uno a uno.

Anziché dividere per ogni numero puoi ridurre il numero di divisioni limitando ai soli numeri primi già trovati perché gli altri sono già multipli di qualcosa.


Quindi, il ragionamento mi porta a dire:

Prepara un vettore (array) in cui memorizzare i numeri primi che troverai, poi fai un ciclo del range in cui vuoi cercare (sempre a partire da 1).
Dividi ogni numero del ciclo per tutti gli elementi del vettore (un secondo ciclo annidato): se non trovi divisioni a resto zero hai trovato un numero primo da aggiungere all'array!

Inviato dal mio Nexus 5 utilizzando Tapatalk

 

[MPG]

Quindi? Metti dentro cose a caso perché le vedi qua o là? La radice ti può servire per fare la fattorializzazione (trovare il minimo comune multiplo: algebra di seconda media!). Ma non basta che la radice sia intera.. per esempio 81 dà 9 ed entrambi non sono numeri primi.. oppure 100!

Inviato dal mio Nexus 5 utilizzando Tapatalk

No intendevo dire che l'ha messo come riferimento il professore mio di informatica per questo problema per cui devo applicarlo, solo che non avevo ben capito..
se poi dici che il professore ha sbagliato non so che dire oltre pero'...

 

[DispatchCode]

Quindi? Metti dentro cose a caso perché le vedi qua o là? La radice ti può servire per fare la fattorializzazione (trovare il minimo comune multiplo: algebra di seconda media!). Ma non basta che la radice sia intera.. per esempio 81 dà 9 ed entrambi non sono numeri primi.. oppure 100!

Inviato dal mio Nexus 5 utilizzando Tapatalk

Non ho capito bene il tuo intervento, probabilmente, in quanto per sapere se N è primo non è errato verificare che un fattore sia <= alla radice quadrata di N.
Nel caso ad esempio del valore 81, non serve scorrere sino a 81; se giunti alla radice di 81 (che è 9, appunto) non si trova un valore che lo divide allora si conclude che è primo; qui appunto sqrt(81) = 9 e 9 è un divisore di 81, quindi 81 non è primo.
Che intendevi tu?

 

[MPG]

Non ho capito bene il tuo intervento, probabilmente, in quanto per sapere se N è primo non è errato verificare che un fattore sia <= alla radice quadrata di N.
Nel caso ad esempio del valore 81, non serve scorrere sino a 81; se giunti alla radice di 81 (che è 9, appunto) non si trova un valore che lo divide allora si conclude che è primo; qui appunto sqrt(81) = 9 e 9 è un divisore di 81, quindi 81 non è primo.
Che intendevi tu?

Era questo che volevo sapere, la spiegazione dell'applicazione, mi interessava esattamente quanto mi hai spiegato, grazie.

 

[rctimelines]

No intendevo dire che l'ha messo come riferimento il professore mio di informatica per questo problema per cui devo applicarlo, solo che non avevo ben capito..
se poi dici che il professore ha sbagliato non so che dire oltre pero'...

Ma tu non lo hai applicato nel tuo primo post! Io non ho detto che il professore abbia sbagliato, lo hai detto tu, solo che decontestualizzata quella operazione non ha senso.

Inviato dal mio Nexus 5 utilizzando Tapatalk

 

[MPG]

Nel primo post cercavo solo una soluzione alternativa personale perchè il prof aveva in caso chiesto di farlo a modo nostro per poi valutare gli errori.

 

[rctimelines]

Non ho capito bene il tuo intervento, probabilmente, in quanto per sapere se N è primo non è errato verificare che un fattore sia Nel caso ad esempio del valore 81, non serve scorrere sino a 81; se giunti alla radice di 81 (che è 9, appunto) non si trova un valore che lo divide allora si conclude che è primo; qui appunto sqrt(81) = 9 e 9 è un divisore di 81, quindi 81 non è primo.
Che intendevi tu?

No, non hai capito. Ho detto che in teoria DOVRESTI dividere ogni numero per TUTTI i suoi precedenti, poi ottimizzi in vari modi: per esempio eliminando tutti i multipli precedenti e limitandosi a dividere solo per i numeri primi precedenti (sui primi 100 numeri riduci a qualche decina di divisioni).
In effetti puoi ridurre ulteriormente il numero limitando il range da analizzare cioè mettendo alla prova divisione per i numeri primi solo i numeri che non sono quadrato di un altro (essendo questa una prova del fatto che sono dei multipli).. potresti eliminarne altri togliendo le radici cubiche... oppure i divisibili per 2 per 3 e per 5... Per ogni ciclo fai sempre Delle operazioni fisse preliminari, ma alla lunga diminuisci quelle complessive.



Inviato dal mio Nexus 5 utilizzando Tapatalk

 

[DispatchCode]

Si, quella parte mi era chiara, e condivido (ad esempio in merito ai Crivelli). Leggendola così sembrava escludessi le radici, ecco il motivo del mio intervento. ;)

 

[rctimelines]

Si, quella parte mi era chiara, e condivido (ad esempio in merito ai Crivelli). Leggendola così sembrava escludessi le radici, ecco il motivo del mio intervento. ;)

:) certo, al contrario, intendevo usare la radice per eliminare dall'analisi i quadrati, ma si possono eliminare anche i cubi e soprattutto i pari: cioè il ciclo principale deve assolutamente avere step +2.. e così da 1 a 1000 hai già 500 numeri da analizzare .. da questi togli ancor prima quadrati e magari anche i cubi e i divisibili per 3, per 5, per 7 e per 11 (che sarebbero divisioni che il secondo ciclo farebbe comunque).. ti resta un centinaio di numeri da verificare!

Inviato dal mio Nexus 5 utilizzando Tapatalk

 

[Andretti60]

La radice quadrata non serve a niente.

Sinceramente non capisco come tu faccia a dire questo. Indipendentemente se si ottimizza o meno, la radice quadrata del numero in esame è il massimo numero per cui si deve dividere.

 

[rctimelines]

Sinceramente non capisco come tu faccia a dire questo. Indipendentemente se si ottimizza o meno, la radice quadrata del numero in esame è il massimo numero per cui si deve dividere.

Vero. Il limite superiore dei divisori è dato dal numero primo < della radice del numero. È una ottimizzazione anche questa.

Inviato dal mio Nexus 5 utilizzando Tapatalk

 

[BAT]

L'esercizio "verifica se n è primo" è un classico esercizio di base che non è possibile effettuare in modo ottimale dal punto di vista computazionale (servono conoscenze matematiche troppo avanzate per uno studente). Quindi ci si limita a considerare il metodo più o meno "a forza bruta" del controllo dei divisori dispari fino al massimo della radice quadrata.

Per quanto riguarda i divisori da controllare puoi consultare il mio intervento qui (come ti hanno già anticipato, la radice quadrata è il divisore massimo da controllare, posto che fai altre ottimizzazioni come controllare solo i divisori dispari):
https://forum.tomshw.it/threads/numero-primo.688373/post-6645134
per quanto riguarda la radice quadrata, leggi attentamente qui:
https://forum.tomshw.it/threads/numero-primo.688373/post-6649177
Il controllo, anche se ottimizzato, funziona bene solo per numeri relativamente piccoli, diciamo sugli int a 32 bit, a patto di usare la radice quadrata su un long double (almeno a 64 bit). La ragione è che un floating point a 64 bit ha almeno 13 cifre di precisione (normalmente 15), più che sufficienti per calcolare con tutte le cifre necessarie la radice quadrata di un int a 32 bit.
In passato, ho letto alcuni (inquietanti) post dove, per "allargare" l'intervallo di controllo suigli interi, veniva erroneamente suggerito agli utenti di usare unsigned oppure long/unsigned long (64 bit). Ma se controlli un intero a 64 bit, l'arrotondamento/troncamento per difetto di una radice quadrata a 64 bit potrebbe far saltare il controllo su un bel po' di numeri dispari... qualcuno dei quali potrebbe essere un divisore del numero da controllare, col nefasto risultato di dire TRUE (il numero è primo) su un numero che invece non lo è!

 

[rctimelines]

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à.

Se poi fai anche alcune verifiche preliminari sul numero per escluderlo ancor prima di iniziare a fare il ciclo delle divisioni, la velocità può aumentare ancora. Per esempio 121, se lo escludi da subito con una radice quadrata (che devi comunque fare per calcolare il limite dei valori per cui dividere), ti risparmia 3 divisioni.
Oppure, se hai possibilità di fare velocemente una radice cubica, puoi eliminare a priori altri numeri, come per esempio il 343 ne risparmi 6: per 3,5,7,11,13,17.. se facessi con tutti i dispari addirittura 8 (di cui 2!non servono). Ovviamente in tal caso aggiungi una onerosissima radice cubica per ogni numero che passa la necessaria radice quadrata... bisogna vedere se porta davvero benefici.

Magari ti conviene fare un filtro con cui prepari la lista di numeri da verificare: dato un range di valori elimini i numeri pari e i cubi... poi passi alla verifica il vettore che rimane dividendo ogni numero per tutti i numeri primi minori della radice del numero stesso.

Questo algoritmo mi ispira! Oggi vedrò se trovo il tempo implementarlo in turbo-pascal 2.0 oppure con il "locomotive basic" :) :) :)
Anzi no, ne faccio una versione in C standard così la provo su un Amiga 500, su un 486/66, su un Pentium II e su un i7-3770..


Inviato dal mio Nexus 5 utilizzando Tapatalk

 

[MPG]

Caspita rctimelines sei ad un livello troppo alto per me, non so se sei laureato in informatica o insegni ma tieni presente che spesso chi ha bisogno (come me che sono alle superiori non all'università e che informatica pe rme è ostica ) ha bisogno di spiegazioni meno complesse altrimenti si fa ancora piu' fatica a capire.
Per esempio attendevo la spiegazione come al post 18 per capire l'uso dell'sqrt, ci sono vari livelli di conoscenza , pensa sia utile pensare che chi scrive chiedendo aiuto non sia "eccelso" in informatica.

 

[rctimelines]

Caspita rctimelines sei ad un livello troppo alto per me, non so se sei laureato in informatica o insegni ma tieni presente che spesso chi ha bisogno (come me che sono alle superiori non all'università e che informatica pe rme è ostica ) ha bisogno di spiegazioni meno complesse altrimenti si fa ancora piu' fatica a capire.
Per esempio attendevo la spiegazione come al post 18 per capire l'uso dell'sqrt, ci sono vari livelli di conoscenza , pensa sia utile pensare che chi scrive chiedendo aiuto non sia "eccelso" in informatica.

No, sono della "vecchia acuola" (quella non nativa digitale) e quindi spesso mi capita di confondere chi oggi partecipa ad un forum come gli utenti delle vecchie BBS che erano smanettoni smaliziati che ne sapevano una più del diavolo! Comunque capisco la tua situazione, mi scuso per l'arroganza e ti prego di considerarla in maniera amichevole e non troppo sul serio, come deve essere in questi contesti!
Cerca di capire ciò che ti ho scritto sopra, spero che ti possa essere utile per fare bella figura a scuola ma soprattutto per comprendere come ottimizzare un algoritmo in generale: parti da una buona comprensione della teoria e poi ci ragioni sopra. Cerca in internet ma segui criticamente i consigli e l'autorità di chi li dà: no chi dice l come premessa che non sa bene di cosa sta parlando (vedi sopra)! Se per esempio cercavi su Google "crivello di Eratostene", come ti ho detto già all'inizio, avresti trovato spiegazione a tutto ciò che ti serviva.. magari il tuo prof voleva questo!

Inviato dal mio Nexus 5 utilizzando Tapatalk