Cosa sono i numeri primi? I numeri primi sono numeri naturali maggiori di 1 che sono divisibili solo per 1 e per se stessi. Lo sappiamo dai tempi della scuola e ce lo ripetiamo a menadito, ma spesso tendiamo a sottovalutare le conseguenze pratiche che questo aspetto ha nella vita di ogni ogni giorno.
- 1) Teorema del quoziente e del resto
- 2) Teorema fondamentale dell’aritmetica
- 3) Come determinare se un numero è primo
- 4) Crivello di Eratostene
- 5) Crivello di Eratostene in Python
- 6) Primi 100 numeri primi
- 7) Tavola dei primi 200 numeri primi
- 8) Numeri primi fino a 1000
- 9) Approfondimento: numeri primi e crittografia
Teorema del quoziente e del resto
In matematica esiste il teorema del quoziente e del resto secondo il quale se fissiamo a e b come numeri naturali, per cui a può essere un qualsiasi numero naturale mentre invece b può essere un qualsiasi numero naturale diverso da zero, sarà sempre possibile trovare due numeri numeri q e r, unici, tali che si possono esprimere come il prodotto di b per q più r, con r minore strettamente di b.
Scritto in formule avremo:
q, r ∈ N;
a = b × q + r
r < b
Come sappiamo q ed r vengono chiamati quoziente e il resto di a per b. Se r uguale a zero la divisione sarà esatta, mentre invece serve maggiore di zero avrà un resto r.
E a questo punto entrano in gioco i numeri primi: da quello che abbiamo scritto possiamo convenire che ogni numero sia divisibile per uno e per se stesso, dato che si può sempre esprimere come prodotto di uno per a. Ogni numero B sarà diviso divisore di zero dato che B per zero fa sempre zero. Se consideriamo numeri strettamente maggiori di 1, a questo punto, troveremo alcuni numeri che sono multipli solo di uno e di se stessi che vengono detti numeri primi, mentre ce ne saranno altri che ammettono ulteriori divisori che sono detti numeri composti.
Teorema fondamentale dell’aritmetica
Saranno quindi i primi numeri 2,3, 5,7, 11,13, mentre invece saranno numeri composti quattro, 6, 8. 9, 10, 12, esattamente come 365 oppure 996. L’irregolarità della distribuzione tra numeri primi e numeri composti (diversa da quella più netta tra numeri pari e dispari, ad esempio) è sicuramente degna di interesse per i matematici, ma anche per gli informatici che si occupano di crittografia. Per comprendere a questo punto cosa sono davvero numeri numeri primi bisogna considerare la base teorica su cui si fondano i numeri numeri composti, ovvero il teorema fondamentale dell’aritmetica. Senza entrare nei dettagli tecnici della dimostrazione, il teorema afferma che ogni numero naturale strettamente maggiore di uno si può decomporre nel prodotto di fattori primi, e tale rappresentazione non soltanto esiste sempre ma è unica a meno dell’ordine.
In termini più semplici, il teorema afferma che qualsiasi numero naturale (> 1) può essere espresso come il prodotto di numeri primi, e questa rappresentazione è unica, nel senso che se prendi due diverse decomposizioni di un numero naturale nei suoi fattori primi, queste differiranno solo nell’ordine in cui sono scritti i fattori primi.
Ad esempio, prendiamo il numero 60. La sua decomposizione in fattori primi è:
60=2×2×3×5
Questo significa che 60 può essere espresso come il prodotto dei fattori primi 2, 3 e 5. Se provassimo a decomporre 60 in fattori primi in un altro modo, otterremmo ancora gli stessi fattori primi, ma potrebbero essere disposti in un ordine diverso:
60=3×5×2×2
Anche se l’ordine dei fattori primi è diverso, i fattori stessi sono gli stessi: 2, 3 e 5. Questa è l’unicità della decomposizione in fattori primi garantita dal Teorema Fondamentale dell’Aritmetica. Analogamente:
e così via, il che suggerisce che ogni scomposizione in fattori prima sia univoca, una sorta di “codice fiscale” di ogni numero. Secondo il Teorema Fondamentale dell’Aritmetica, ogni numero naturale maggiore di uno ha una sola scomposizione in fattori primi, e questa scomposizione è unica a meno dell’ordine dei fattori.
Quindi, due scomposizioni in fattori primi che rappresentano lo stesso numero devono avere gli stessi fattori primi, anche se possono essere disposti in ordine diverso.
Come determinare se un numero è primo
Storicamente le prime tecniche per determinare il suo numero primo si devono agli antichi greci: l’algoritmo autorizzato era parecchio elementare, in effetti, e consisteva semplicemente nel provare tutti i numeri fino ad arrivare a quello dato. Anche senza conoscere la teoria della complessità computazionale, si noti, è chiaro che è più grande il numero più tempo impiegherà all’algoritmo a concludere le proprie considerazioni.
Per ogni possibile numero naturale N maggiore di uno:
- come primo passo proveremo a dividere N per due, per tre, … per N-1;
- non appena una delle divisioni producesse resto zero prenderemo nota del quoziente q, e ricorderemo che può essere espresso come b × q (dove si intende che B sia il valore che abbiamo trovato tra quelli del passo uno);
- Se invece tutte le divisioni producessero il resto non nullo concluderemmo che N è effettivamente un numero primo.
Crivello di Eratostene
Il crivello di Eratostene è un antico algoritmo per trovare tutti i numeri primi fino a un certo limite. Questo metodo è stato sviluppato da Eratostene, un matematico greco antico.
In parole semplici, il crivello di Eratostene funziona in questo modo:
- Si prende una lista di numeri da 2 fino al limite desiderato.
- Si inizia con il primo numero della lista (che è il numero 2) e si cancellano tutti i suoi multipli dalla lista, lasciando solo il 2 e i suoi multipli.
- Si passa al prossimo numero nella lista ancora non cancellato (il 3), e si cancellano tutti i suoi multipli dalla lista.
- Si continua questo processo fino a quando non si arriva all’ultimo numero nella lista.
Alla fine, rimarranno solo i numeri primi nella lista.
Crivello di Eratostene in Python
In questo codice Python, la funzione crivello_eratostene
restituisce una lista di numeri primi fino al limite specificato. Utilizza un approccio simile a quanto descritto sopra: crea una lista di booleani inizializzati a True
per indicare che tutti i numeri inizialmente sono considerati primi. Poi, attraverso un doppio ciclo, identifica i numeri non primi impostando a False
i loro multipli. Alla fine, restituisce una lista contenente solo i numeri primi trovati.
def crivello_eratostene(limite): numeri = [True] * (limite + 1) numeri[0] = numeri[1] = False # 0 e 1 non sono primi for i in range(2, int(limite ** 0.5) + 1): if numeri[i] == True: for j in range(i*i, limite + 1, i): numeri[j] = False primi = [num for num in range(2, limite + 1) if numeri[num] == True] return primi # Utilizzo dell'algoritmo con limite 50 come esempio limite = 50 numeri_primi = crivello_eratostene(limite) print("Numeri primi fino a", limite, ":", numeri_primi)
Primi 100 numeri primi
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541
Tavola dei primi 200 numeri primi
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233,
239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419,
421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607,
613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811,
821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019,
1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103,
1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223,
1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319,
1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453,
1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567
Numeri primi fino a 1000
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997
Approfondimento: numeri primi e crittografia
Esistono altri algoritmi più efficienti per trovare i numeri primi senza esaminare tutte le combinazioni fino a un certo limite, come fa l’approccio se vogliamo “ingenuo” di Eratostene. Un esempio è il “test di primalità di Miller-Rabin” che è più veloce solo per numeri molto grandi. Questo test non esamina tutte le combinazioni, ma si basa su concetti più complessi della teoria dei numeri per identificare se un numero è primo o no. Altri algoritmi come il “crivello quadrato”, ad esempio, sono più efficienti del crivello di Eratostene per numeri molto grandi.
In generale, trovare numeri primi molto grandi è un problema difficile e ci sono continui sviluppi in teoria dei numeri e in informatica per rendere la ricerca dei numeri primi più efficiente, soprattutto quando si tratta di numeri estremamente grandi utilizzati in crittografia e in altre aree della matematica e della scienza computazionale.
👇 Da non perdere 👇
- Gratis 🎉
- intelligenza artificiale 👁
- Internet 💻
- Marketing & SEO 🌪
- Mondo Apple 🍎
- Reti 💻
- Scrivere 🖋
- 💬 Il nostro canale Telegram: iscriviti
- 🟢 6 domande frequenti in ambito SEO, con risposte
- 🟢 Domini .APPLE, cosa sono e come funzionano
- 🔵 Come si accede a Plesk sul mio sito