Guida pratica ai numeri primi

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.

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:

$56=2\times 2\times 2\times 7$

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:

1. come primo passo proveremo a dividere N per due, per tre, … per N-1;
2. 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);
3. 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:

1. Si prende una lista di numeri da 2 fino al limite desiderato.
2. 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.
3. Si passa al prossimo numero nella lista ancora non cancellato (il 3), e si cancellano tutti i suoi multipli dalla lista.
4. 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 👇

• 📈 Analizza Cellulari 📱
• 🔐 AI che dolor, Chat 🏴
• 🎯 Targetizza Database SQL 🗄
• 📊 Analizza Errori più comuni 📛
• 🚧 Costruisci Evergreen 📟
• 👩‍💻 Programma Gratis 🎉
• 💻 Configura Hosting a confronto 💑
• 🔒 Conosci Hosting reti e domini 💻
• 👩‍💻 Tapioca Informatica 🖥
• 💻 Iconizza Internet 💻
• 🔒 Gestisci Lavoro 🔧
• 💡 Mostra Marketing & SEO 🌪
• 🔑 Apprendi Meteo ⛅
• 🤯 Visiona Mondo Apple 🍎
• 🔍 Supervisiona Mondo Domini 🌐
• 🚀 Metti in cloud monitoraggio servizi online 📈
• 🔮 Anatomizza Nuove tecnologie 🖥
• 🔒 Antani PEC e firma digitale 📩
• 👀 Prematura Programmare 🖥
• 🎮 Lonfa Scrivere 🖋
• 🔒 Conosci Servizi di SMS 📶
• 👀 Guarda Sicurezza informatica e privacy digitale 🖥
• 🎮 Ricorda Siti web 🌎
• 🤖 Ottimizza Spiegoni artificiali 🎓
• 🧠 Neuralizza Svago 🎈
• 📡 Quantizza Usare Excel 🌀
• 🤖 Sovrascrivi Windows 😲
• 🎨 Personalizza Wireless 🚁
• 🔑 Decifra WordPress 🤵
• 💬 Il nostro canale Telegram: iscriviti
• 🔴 Coding: definizione, significato, motivazioni
• 🟢 Che cos’è una subnet mask (con esempi pratici)
• 🔴 Coding: definizione, significato, motivazioni

---

---

Questo sito esiste da 4469 giorni (12 anni), e contiene ad oggi 7463 articoli (circa 5.970.400 parole in tutto) e 13 servizi online gratuiti. – Leggi un altro articolo a caso Non ha ancora votato nessuno.