{"id":173,"date":"2023-07-15T18:20:53","date_gmt":"2023-07-15T18:20:53","guid":{"rendered":"https:\/\/mathority.org\/it\/setaccio-deratostene\/"},"modified":"2023-07-15T18:20:53","modified_gmt":"2023-07-15T18:20:53","slug":"setaccio-deratostene","status":"publish","type":"post","link":"https:\/\/mathority.org\/it\/setaccio-deratostene\/","title":{"rendered":"Cos'\u00e8 il metodo del setaccio di eratostene?"},"content":{"rendered":"

Il metodo Eratostene Sieve<\/strong> \u00e8 un algoritmo matematico utilizzato per trovare tutti i numeri primi<\/a> inferiori a un dato numero. Questo sistema fu sviluppato dal matematico greco Eratostene oltre 2.000 anni fa.<\/p>\n

Un numero primo \u00e8 un numero naturale maggiore di 1 che ha solo due divisori: 1 e se stesso. Ad esempio, il numero 2 \u00e8 primo, poich\u00e9 \u00e8 divisibile solo per 1 e 2. Il numero 4, invece, non \u00e8 primo, poich\u00e9 \u00e8 divisibile per 1, 2 e 4.<\/p>\n

In generale, il metodo del setaccio di Eratostene \u00e8 un modo efficace per trovare tutti i numeri primi inferiori a un dato numero. Per fare ci\u00f2, viene utilizzata una lista di numeri<\/strong> e tutti i multipli dei numeri primi trovati vengono cancellati. Alla fine del processo, i numeri che non sono stati cancellati sono i numeri primi.<\/p>\n

Come funziona il setaccio Eratostene?<\/span><\/h2>\n

Il crivello di Eratostene \u00e8 un concetto potente che pu\u00f2 essere utilizzato per trovare molti numeri primi in modo relativamente rapido e semplice<\/strong> . Funziona secondo un principio semplice: qualsiasi multiplo di un numero primo non pu\u00f2 essere un numero primo. Ad esempio, poich\u00e9 3 \u00e8 primo, 6, 9, 12, 15 e tutti gli altri multipli di 3 non possono essere numeri primi.<\/p>\n

Quando si tenta di identificare i numeri primi tra due numeri interi dati o di cercare nuovi numeri primi, tutti i multipli dei numeri primi<\/strong> potrebbero essere aggiornati prima ancora che la ricerca abbia inizio.<\/p>\n

Il setaccio di Eratostene funziona come un filtro, rimuovendo i multipli di tutti i numeri primi precedenti dall’elenco dei numeri in modo da non perdere tempo a testarli.<\/p>\n

Per comprendere meglio questo metodo \u00e8 necessario utilizzare un esempio pratico. Vediamo di seguito come trovare tutti i numeri primi minori di 20<\/strong> nel modo seguente:<\/p>\n

    \n
  1. Scrivi un elenco di numeri da 2 a 20: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20.<\/li>\n
  2. Rimuovi tutti i multipli di 2: 2, 3, 5, 7, 9, 11, 13, 15, 17, 19.<\/li>\n
  3. Elimina tutti i multipli di 3: 2, 3, 5, 7, 11, 13, 17, 19.<\/li>\n
  4. Ignora tutti i multipli di 5: 2, 3, 5, 7, 11, 13, 17, 19.<\/li>\n
  5. Cancella tutti i multipli di 7: 2, 3, 5, 7, 11, 13, 17, 19.<\/li>\n<\/ol>\n

    I numeri non incrociati sono primi: 2, 3, 5, 7, 11, 13, 17, 19.<\/p>\n

    Esempi pratici per trovare i numeri primi utilizzando il crivello di Eratostene<\/span><\/h2>\n

    Rispetto ad altri metodi per trovare i numeri primi, il setaccio Eratostene \u00e8 veloce e facile da usare<\/strong> . Soprattutto quando i computer non sono disponibili. Per il processo non sono richiesti divisioni, moltiplicazioni o fattori di ricerca.<\/p>\n

    In entrambi i casi, il crivello elimina rapidamente i numeri che sicuramente non sono primi. Il concetto di questo metodo si basa sul fatto che ogni numero pu\u00f2 essere diviso in fattori<\/strong> . Questi fattori possono poi essere divisi, se necessario, fino a quando rimangono solo i fattori primi.<\/p>\n

    Questa si chiama scomposizione in fattori primi di un numero. Un tale processo indica che tutti i numeri non primi hanno un insieme unico di fattori primi.<\/p>\n

    In altre parole, qualsiasi numero non primo ha come fattore un numero primo. Una volta identificato un numero primo, tutti i suoi multipli possono essere automaticamente considerati non primi<\/strong> . Il setaccio Eratostene \u00e8 un metodo per eliminarli. Consideriamo ad esempio i numeri primi compresi tra 1 e 30:<\/p>\n

    La prima cosa che devi capire \u00e8 che i numeri primi sono quelli che sono divisi per il numero 1 e se stessi. Ci\u00f2 premesso, prendiamo l’esempio del crivello di Eratostene:<\/p>\n

      \n
    1. Disegna una tabella con i numeri da 1 a 30. <\/li>\n<\/ol>\n
      \n\n\n\n\n\n\n\n\n
      1<\/td>\n 2<\/td>\n 3<\/td>\n 4<\/td>\n 5<\/td>\n<\/tr>\n
      6<\/td>\n 7<\/td>\n 8<\/td>\n 9<\/td>\n dieci<\/td>\n<\/tr>\n
      undici<\/td>\n 12<\/td>\n 13<\/td>\n 14<\/td>\n quindici<\/td>\n<\/tr>\n
      16<\/td>\n 17<\/td>\n 18<\/td>\n 19<\/td>\n venti<\/td>\n<\/tr>\n
      ventuno<\/td>\n 22<\/td>\n 23<\/td>\n 24<\/td>\n 25<\/td>\n<\/tr>\n
      26<\/td>\n 27<\/td>\n 28<\/td>\n 29<\/td>\n 30<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n