Calcolatrice dei numeri primi

n è primo <=> d(n) = 2; previousPrime(97) = 97; nextPrime(97) = 97; nextPrime(1000000) = 1000003

n

Il numero intero in esame — da 2 a 1.000.000. Il limite inferiore è voluto e non ereditato: il primo precedente di 1 non esiste, quindi una pagina che accettasse 1 avrebbe una riga che non potrebbe riempire onestamente. Se 1 sia primo è una questione di definizione e trova risposta nelle domande qui sotto invece che nella calcolatrice. I numeri negativi e i decimali vengono rifiutati

d(n)

Il numero di divisori positivi, che è la prima riga del risultato e l'unica prova su cui poggia il verdetto. d(n) = 2 significa che lo dividono esattamente due numeri, che è la definizione di numero primo. Il conteggio viene dalla routine condivisa di teoria dei numeri, quindi è lo stesso valore che la pagina dei fattori e quella della scomposizione riportano per lo stesso ingresso

d(n) = 2

Il test stesso, enunciato come equazione. È un'equivalenza e non un'approssimazione: un numero è primo se e solo se ha esattamente due divisori. Per 97 i divisori sono 1 e 97, quindi il conteggio è 2 e il badge legge primo. Per 100 sono 1, 2, 4, 5, 10, 20, 25, 50 e 100, quindi il conteggio è 9 e il badge legge composto

previousPrime(n)

Il più grande primo minore o uguale a n. È inclusivo in alto, quindi quando n è primo la risposta è n stesso. Per 100 la risposta è 97; per 25 è 23; per 97 è 97. L'intervallo è chiuso perché l'alternativa richiederebbe una regola per che cosa stampare quando n è già primo, e una riga vuota in un pannello dei risultati si legge come un guasto invece che come un fatto

nextPrime(n)

Il più piccolo primo maggiore o uguale a n, con la stessa regola inclusiva in basso. Per 25 è 29, per 100 è 101 e per 97 è 97. Questo può uscire dall'intervallo dell'ingresso: nextPrime(1000000) è 1000003, un primo più grande di qualunque numero la pagina accetti, e viene riportato come risposta invece di essere trattato come fuori dai limiti

da 1e6 a 1e6 + 100

L'intorno del tetto dell'ingresso, e perché lassù serve un test separato. I primi vicini a un milione sono 999.983 e 1.000.003, quindi la ricerca che parte da 1.000.000 deve guardare oltre il milione in una direzione. La routine che conta i divisori rifiuta argomenti sopra un milione e solleverebbe un'eccezione, quindi la ricerca dei vicini usa un test proprio che non ha quel limite — e i due devono concordare ovunque si sovrappongano, ed è quello che controllano le righe sui primi negli esempi

Scegliere un modulo è il motivo più pratico per volere un numero primo vicino a un numero che hai già scelto. Il numero di caselle di una tabella hash si prende di solito primo, perché un modulo primo sparpaglia le chiavi che condividono un fattore comune invece di farle collidere; una tabella dimensionata 1000 manda tutti i multipli di 25 nelle stesse poche posizioni, mentre una dimensionata 997 no. Lo stesso istinto vale in crittografia, dove le chiavi si costruiscono da primi grandi e lontani fra loro. Controllare se un numero è primo risolve anche in fretta le domande di divisibilità: se un numero non ha divisori primi fino alla sua radice quadrata non ne ha nessuno, e il badge risponde in un passo invece che per tentativi. Certi rompicapi riguardano semplicemente la primalità — i primi gemelli, le distanze fra primi consecutivi e se un dato numero sia il prodotto di due primi. Quando poi la domanda si rivela riguardare i fattori stessi, la pagina della scomposizione spezza il numero in primi ed è la tappa successiva naturale; quando riguarda quali numeri dividono il tuo, la pagina dei fattori li elenca tutti; e quando il numero in esame non è primo e vuoi sapere di che cosa è fatto, il conteggio dei divisori di questa pagina è il primo indizio invece della risposta completa.

1. Un numero primo: 97

   1. Prova i divisori di 97: 2 non lo divide, e nemmeno 3, 5, 7 o 11
   2. Fermati alla radice quadrata: 10 × 10 = 100 ha già superato 97, quindi non resta niente da provare
   3. Gli unici divisori sono 1 e 97, quindi il conteggio è 2 e il numero è primo
   4. Il primo precedente è 97 stesso, perché 97 è già primo e la ricerca è inclusiva
   5. Anche il primo successivo è 97, per lo stesso motivo

   L'ingresso predefinito, e l'illustrazione più pulita della regola inclusiva. Entrambi i vicini tornano come il numero stesso, cosa che a prima vista sembra che le due righe non abbiano fatto niente. L'hanno fatto: il più grande primo non maggiore di 97 è 97, e il più piccolo primo non minore di 97 è 97 anche lui. L'alternativa — una disuguaglianza stretta — lascerebbe queste due righe senza niente da stampare proprio sugli ingressi in cui la pagina è più sicura, e una riga vuota in un pannello dei risultati si legge come un errore. Questo caso è anche il punto in cui i due test indipendenti della pagina si incontrano: il conteggio dei divisori dice 2, e la ricerca dei vicini concorda che 97 è primo, e per arrivarci usano codice diverso.

2. Un numero composto: 100

   1. 100 è pari, quindi 2 lo divide; finisce con 00, quindi lo dividono anche 4, 5, 10, 20, 25 e 50
   2. I divisori sono 1, 2, 4, 5, 10, 20, 25, 50 e 100 — nove
   3. Nove è più di due, quindi il badge legge composto e non primo
   4. Il più grande primo minore o uguale a 100 è 97; il più piccolo maggiore o uguale è 101
   5. Entrambi i vicini stanno a un passo fuori dal numero, ed è l'aspetto che ha un numero composto in mezzo a una lacuna

   Il caso che mostra i vicini fare un lavoro vero. Quando un numero è composto le due righe sono l'output utile, perché rispondono alla domanda che il lettore ha subito dopo: se non questo numero, allora quale? Novantasette e centouno sono i primi più vicini, e 100 sta in mezzo a loro. Vale la pena guardare anche il conteggio dei divisori, nove: è dispari, cosa che succede esattamente quando il numero è un quadrato perfetto, e 100 è 10 al quadrato. Quindi un solo sguardo al conteggio ti dice già qualcosa sulla forma del numero, prima di qualsiasi scomposizione.

3. Un numero appena oltre un primo: 25

   1. I divisori di 25 sono 1, 5 e 25 — tre, perché il 5 si accoppia con se stesso
   2. Tre è più di due, quindi 25 è composto
   3. Scendi da 25: 24, 23 — 23 è primo, quindi è il primo precedente
   4. Sali da 25: 26, 27, 28, 29 — 29 è primo, quindi è il primo successivo
   5. La distanza qui è sei in tutto: 23 e 29 stanno ai due lati di 25

   Un quadrato perfetto, ed è per questo che il conteggio dei divisori è dispari, e un caso in cui i due vicini stanno a distanze visibilmente diverse — due sotto e quattro sopra. Il conteggio di tre mostra anche perché due sia la soglia giusta invece di un conteggio dei fattori primi: 25 ha un solo fattore primo, il 5, ma non è primo, e il numero di divisori se ne accorge senza dover guardare affatto la scomposizione.

L'ingresso deve essere un numero intero da 2 a 1.000.000. Zero e uno vengono rifiutati, e uno viene rifiutato per un motivo diverso dallo zero: è una questione di definizione e non un numero fuori intervallo, e il primo precedente di 1 non esiste. I numeri negativi vengono rifiutati — la primalità è una proprietà dei numeri interi maggiori di 1, e anche se in alcuni rami della matematica esiste una convenzione per i primi negativi, questa pagina non ne adotta nessuna. I decimali vengono rifiutati invece di essere arrotondati. Il tetto di un milione vale solo per l'ingresso; le due righe dei vicini possono legittimamente riportare un primo fuori da esso, e il primo successivo di un milione è 1.000.003, che viene riportato invece che rifiutato. Il test che sta dietro al verdetto è la divisione per tentativi fino alla radice quadrata, che a questa dimensione è immediata e su un numero di venti cifre è disperata, e quel confine è una proprietà del problema e non di questa implementazione. La pagina riporta tre numeri e un badge: non elenca i divisori stessi, non scompone in fattori un numero composto e esamina un numero alla volta invece di un intervallo. Le tabelle di riferimento qui sotto sono righe fisse e non una risposta al tuo ingresso. Infine, un numero primo viene riportato come il proprio primo precedente e il proprio primo successivo, il che è una scelta deliberata di un intervallo inclusivo e non due righe che non hanno trovato niente.

1 è un numero primo?

No, e non è nemmeno un numero composto. Un numero primo è definito come un numero intero maggiore di 1 con esattamente due divisori positivi, e 1 ne ha uno solo, quindi fallisce la definizione su entrambi i fronti. È una scelta fatta deliberatamente e non una svista: se 1 fosse contato come primo, l'affermazione che ogni numero ha esattamente una scomposizione in fattori primi smetterebbe di essere vera, perché potresti moltiplicare una scomposizione per 1 quante volte vuoi. Escludere 1 è ciò che tiene pulito quel teorema. Dato che è una questione di definizione e non di aritmetica, la pagina non accetta 1 come ingresso: la risposta vive qui.

Perché il primo precedente e il primo successivo tornano entrambi come il numero stesso?

Perché entrambe le ricerche sono inclusive. Il primo precedente è il più grande primo che non è più grande del tuo numero, e il primo successivo è il più piccolo primo che non è più piccolo di esso. Quando il numero è già primo soddisfa entrambe le descrizioni, quindi entrambe le righe lo riportano. L'alternativa sarebbe una disuguaglianza stretta, e allora un ingresso primo lascerebbe due righe senza niente da stampare. Una riga vuota in un pannello dei risultati si legge come qualcosa che è andato storto, e la pagina non riuscirebbe a rispondere proprio nel caso in cui è più sicura di sé. La stessa convenzione compare negli arrotondamenti, dove un numero già alla precisione richiesta torna invariato.

Perché il primo successivo può essere più grande di un milione quando l'ingresso non può?

Perché il tetto è un limite a quello che puoi chiedere, non a quello che può essere la risposta. Il primo successivo di 1.000.000 è 1.000.003, e rifiutarsi di stamparlo significherebbe rifiutarsi di rispondere a una domanda del tutto ben posta su un ingresso che la pagina ha accettato. Quindi la ricerca dei vicini gira su un test proprio, senza limite superiore, mentre il conteggio dei divisori continua a usare la routine condivisa che copre solo l'intervallo. Questo significa che due pezzi di logica decidono entrambi se un numero è primo — uno limitato e uno no — e devono concordare ovunque si sovrappongano, ed è quello che controlla l'esempio del 97: il conteggio dice 2, e la ricerca dei vicini dice che 97 è primo.

A che cosa serve davvero un numero primo?

Soprattutto a dimensionare le cose. Alle tabelle hash si dà di solito un numero primo di caselle, perché un modulo primo sparpaglia le chiavi che condividono un fattore comune — una tabella con 1000 caselle manda tutti i multipli di 25 nelle stesse poche posizioni, mentre una con 997 no. Lo stesso ragionamento vale ovunque un contatore si avvolga: una lunghezza di ciclo che è prima evita di risuonare con schemi regolari nei dati. La crittografia è l'altro grande impiego, dove le chiavi si costruiscono da primi sia molto grandi sia molto distanti fra loro, e la sicurezza si regge su quanto è difficile riscomporre il loro prodotto nei due primi da cui viene. Gli usi più piccoli sono dappertutto: verificare un'affermazione di divisibilità, controllare se un numero è il prodotto di due primi, e i rompicapi classici sui primi gemelli e sulle distanze fra primi consecutivi.

Come decide la pagina, e quanto è sicura?

Contando i divisori, il che è esatto e non probabilistico. Un numero è primo se e solo se ha esattamente due divisori positivi, quindi il conteggio chiude la questione senza possibilità di risposta sbagliata e senza doversi fidare di un test che potrebbe essere ingannato. Il conteggio si fa per divisione per tentativi fino alla radice quadrata, ed è per questo che il tetto è un milione: oltre, il metodo diventa lento invece che inaffidabile. Per numeri molto più grandi i metodi esatti sono davvero impraticabili e si usano test probabilistici, ma a questa dimensione non c'è motivo di accettare qualcosa meno della certezza, e la pagina non lo fa.

Perché viene mostrato il numero di divisori invece del solo verdetto?

Perché il conteggio è la ragione del verdetto, e mostrarlo significa che i due non possono mai essere in disaccordo: il badge non è un secondo calcolo ma una lettura del numero stampato accanto. È utile anche da solo. Un conteggio dispari significa che il numero è un quadrato perfetto, dato che la radice quadrata si accoppia con se stessa invece che con un divisore diverso. Un conteggio di 2 è la definizione di numero primo. Un conteggio grande rispetto alla dimensione del numero dice che ha molti fattori piccoli, che è il tipo di numero che raccoglie divisori in fretta. E collega la pagina alle altre: la pagina della scomposizione riporta lo stesso numero di divisori per lo stesso ingresso, ricavandolo dagli esponenti, quindi le due pagine si controllano a vicenda.

• Prime Number — the definition, the divisor-count test, and why 1 is excluded by it — Wolfram MathWorld (United States)
• Prime Gaps — the distances between consecutive primes, and what the neighbourhood of a million looks like — Wolfram MathWorld (United States)
• Composite Number — the complement of the primes, and why 1 belongs to neither group — Wolfram MathWorld (United States)
• Divisibilità — la relazione che decide quali numeri dividono un intero, e da cui dipende il conteggio dei divisori usato qui come test di primalità — Treccani, Istituto della Enciclopedia Italiana (Italia)