Controllare se un numero è primo – un po' più velocemente
Immagina di avere un programma che verifica la primalità di un numero e che è attualmente in uso nella produzione di una grande azienda. Con la crescita rapida dell'azienda e l'aumento degli utenti, il numero di richieste al tuo codice cresce di conseguenza. Ti viene quindi richiesto di ottimizzare il programma e renderlo un po' più veloce, in modo che l'azienda possa gestire il carico dei nuovi utenti in arrivo più rapidamente.
La tua soluzione precedente probabilmente consisteva in:
- Scorrere i numeri da 2 fino a
ncontando il numero di divisori.
- Scorrere i numeri da 2 fino a
ne fermarsi non appena trovavi un divisore.
Tuttavia, ci sono alcuni piccoli accorgimenti che possiamo adottare per rendere la procedura più efficiente:
Ottimizzazione 1:
Invece di verificare tutti i numeri da 2 a
n, possiamo controllare se n è divisibile per 2. Se lo è, sappiamo già che n non è primo; se non lo è, non ha senso controllare tutti gli altri numeri pari (4, 6, 8, 10, 12, ecc.) perché sono comunque multipli di 2.Ottimizzazione 2:
Invece di scorrere da 2 fino a
n, possiamo arrivare solo fino a n/2. Infatti, se il numero è divisibile, il divisore più grande che possa avere (diverso da sé stesso) è n/2. Non troveremo mai divisori utili che siano maggiori di n/2.Possiamo combinare le Ottimizzazioni 1 e 2. Di conseguenza, i numeri candidati diventano tutti i dispari fino a
n/2 (dopo aver già verificato 2). In pratica, questo riduce il set di possibili divisori a circa n/4, rendendo il controllo fino a 4 volte più veloce di un controllo lineare semplice.Queste ottimizzazioni rendono il codice un po' più veloce, ma a livello di complessità l’algoritmo rimane comunque una ricerca lineare di divisori. All'aumentare di
n, il programma dovrà aumentare proporzionalmente il numero di operazioni. Più avanti vedremo come ridurre drasticamente il lavoro da svolgere, evitando che cresca in modo direttamente proporzionale a n.Input
La prima riga dell'input contiene un singolo intero
n (1 ≤ n ≤ ).Output
Il programma deve stampare
Yes se n è primo e No altrimenti.Examples
Ingresso | Uscita |
8 | No |
7 | Yes |
1 | No |
19 | Yes |
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB