martedì 4 febbraio 2014

Crivello di Eratostene

Di seguito una implementazione in Java del metodo del crivello di Eratostene per trovare dato un numero n la lista dei numeri primi fino ad n (http://it.wikipedia.org/wiki/Crivello_di_Eratostene ).

package it.test;
import java.util.*;
public class CrivelloEratostene {
 public static void main(String[] args) {
   System.out.println("Inserire il numero di interi desiderato: ");
         Scanner scan = new Scanner(System.in);
         int num = scan.nextInt();
         List<Integer> listNumbers=new ArrayList<Integer>();
         List<Integer> numbersToExclude=new ArrayList<Integer>();
         for(int i=2;i<num;i++){
          int mul=i;
          if(numbersToExclude.contains(i))
        break;
          if(i==2 || !isPrime(i)){
           for(int j=i;j<num;){
            numbersToExclude.add(j);
            j=j+mul;
           }
          }
         }
         for(int i=2;i<num;i++){
          if(!numbersToExclude.contains(i)){
           listNumbers.add(i);
          }
         }
         System.out.println(String.format("Lista numeri primi fino ad %d  : %s", num,listNumbers));
 }
 public static boolean isPrime(int n){
    for(int i=2;i<n;i++) {
          if(n%i==0)
              return false;
      }
      return true;
 }

}




Nessun commento:

Posta un commento