Verificare se un numero è primo - metodo veloce
Finora, per stabilire se un numero
n è primo o meno, abbiamo sostanzialmente fatto un controllo lineare dei divisori. In altre parole, al crescere di n, il numero di operazioni necessarie per determinare la primalità di n aumenta in proporzione (con un certo fattore costante). Se consideriamo gli scenari peggiori (tutti i casi in cui il numero n risulta primo - ad esempio 51, 107 ecc.), il nostro algoritmo eseguiva circa n/4 operazioni per verificare la primalità di n.Questo significa che se aumentiamo
n di 10 volte, l’algoritmo richiederà 10 volte più operazioni. E se aumentiamo n di 100 volte, effettuerà 100 volte più operazioni. In pratica, il tempo di esecuzione è proporzionale a n. C’è un modo per effettuare questo controllo più rapidamente? Sembra che ci siano ancora molti test ridondanti.Il metodo della :
Immaginiamo che
n abbia un divisore d.In tal caso,
n è divisibile per d e sia d che sono numeri interi. Inoltre, o d o è minore o uguale a . Quindi, quando verifichiamo la primalità, possiamo limitarci a iterare fino a raggiungere invece di . In fondo, ci interessa solamente verificare se esiste un divisore diverso da 1 e n, per cui possiamo esaminarne il più piccolo tra d e . Dato che uno dei due è necessariamente minore di , possiamo fermarci una volta raggiunta .È un enorme miglioramento! Effettuare operazioni anziché
n fa una differenza enorme. Immaginate un algoritmo che impiegherebbe 10 anni (3650 giorni) per completare un calcolo: se lo ottimizziamo per svolgere l’equivalente di operazioni invece di n, impiegherebbe soltanto 2 mesi (61 giorni).Are there better algorithms to check the primality of a number?
Yes! You can read more about them on Algorithms for Competitive Programming. There are algorithms that grow (do more operations as
n increases) logarithmically instead of .Input
The first line of the input contains a single integer
n (1 ≤ n ≤ ).Output
The program should print
Yes if n is prime and No otherwise.Examples
Input | Output |
1 | No |
11 | Yes |
353557 | Yes |
34134741 | No |
902468477 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB