In this post I inform you of the publication of another C example program:
This time I dealt with the Eratosthenes' sieve.

In questo post vi informo della pubblicazione di un altro programma d'esempio in C:
Questa volta mi sono occupato del crivello di Eratostene.

Example program in C, Eratosthenes' sieve

Hello folks, this week there's another program example, this time, it is written in C.
This example is an implementation of the Eratosthenes' sieve.
This algorithm was invented by Eratosthenes of Cyrene, and it is still used to find all the prime numbers in a range between 2 and n (inclusive).
This algorithm can be performed even on a piece of paper, with a pencil.
All together now, pick a sheet and a pencil!

  1. Write down a range from 2 to any n
  2. Consider the first number on the range (that is, 2)
  3. Strike out all the multiples of the number you're considering
  4. If the square of the number you're considering is greater than n then go to step 6
  5. Consider the next NON-STRUCK number and go to step 3
  6. End

Let's make an example:
I take n=30 and write down the range.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

I consider the first element (2), I'll strike out every multiple:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Now, I consider the "next NON-STRUCK" element (3), again, I remove its multiples

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

I continue by considering 5...

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

I can't go further because the square of 7 is greater than n (in fact: 5^2 = 25 < n = 30 < 49 = 7^2), that means that I completed the procedure.

You can probably see that all the NON-STRUCK numbers are prime numbers.
I hope this will be useful.
See you soon!

Update 12/11/2014:
This file has been moved to Sourceforge under the name of "eratosthenes_sieve.c" in the "Sample programs" project.

Go back to the top, Share, Look at the comments or Comment yourself!

Programma d'esempio in C, Crivello di Eratostene

Salve gente, questa settimana c'è un altro programma d'esempio, questa volta scritto in C.
Questo esempio è un'implementazione del crivello di Eratostene.
Questo algoritmo è stato inventato da Eratostene di Cyrene, ed è ancor oggi usato per trovare tutti i numeri primi nell intervallo tra 2 e n (inclusi).
Questo algoritmo si può fare anche su un pezzo di carta, con una matita.
Tutti insieme adesso, prendete un foglio e una matita!

  1. Scrivete un intervallo da 2 ad un qualsiasi n
  2. Considerate il primo numero nell'intervallo (ovvero, 2)
  3. Sbarrate tutti i multipli del numero che state considerando
  4. Se il quadrato del numero che considerate è maggiore di n, andate al passo 6
  5. Considerate il successivo numero NON SBARRATO e andate al passo 3
  6. Fine

Facciamo un esempio:
Prendo n=30 e scrivo l'intervallo.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Considero il primo elemento (2), sbarrerò ogni multiplo:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Ora, considero il "prossimo elemento NON SBARRATO" (3), di nuovo, rimuovo i multipli

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Continuo considerando 5...

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Non posso andare oltre perché il quadrato di 7 è maggiore di n (infatti: 5^2 = 25 < n = 30 < 49 = 7^2), ciò vuol dire che ho completato la procedura.

Potete probabilmente vedere che tutti i numeri NON SBARRATI sono numeri primi.
Spero che questo vi torni utile.
A presto!

Aggiornamento 11/12/2014:
Questo file è stato spostato su Sourceforge con il nome di "eratosthenes_sieve.c" nel progetto "Sample programs".

Torna in cima, Condividi, Guarda i commenti o Commenta tu stesso!