Corso di Informatica 1 (IN110)

Gli esercizi

Testi e soluzioni di alcuni esercizi

Crivello di Eratostene per la ricerca dei numeri primi minori di n

/*
**  eratostene.c
**
**  Stampa i numeri primi minori di N utilizzando
**  il crivello di Eratostene.
**
**  Marco Liverani (liverani@mat.uniroma3.it) - Ottobre 2017
*/

#include <stdlib.h>
#include <stdio.h>
#define MAX 1000

int inizializza(int x[]) {
  int i, n;
  printf("Inserisci n: ");
  scanf("%d", &n);
  for (i=2; i<=n; i++)
    x[i] = 1;
  return(n);
}

void eratostene(int x[], int n) {
  int i, j;
  for (i=2; i<=n; i++)
    if (x[i] == 1)
      for (j=2*i; j<=n; j=j+i)
        x[j] = 0;
  return;
}

void stampaPrimi(int x[], int n) {
  int i;
  for (i=2; i<=n; i++)
    if (x[i] == 1)
      printf("%d\n", i);
  return;
}

int main(void) {
  int a[MAX], n;
  n = inizializza(a);
  eratostene(a, n);
  stampaPrimi(a, n);
  return(0);
}

Author: Marco Liverani - Last modified: Monday October 24, 2016 - URI: http://www.mat.uniroma3.it/users/liverani/IN1/eratostene.shtml