Sieb von Eratosthenes
import java.util.Scanner;
public class BooleanPrimes
{
public static int counter = 0 ;
public static void main(String[] argh)
{
Scanner scanner = new Scanner(System.in);
System.out.println("Enter a number: ");
int size = scanner.nextInt();
boolean[] boolArray = new boolean[size+1];
printArray( generateBoolArray(boolArray,size+1),size);
}
public static boolean[] generateBoolArray(boolean[] boolArr, int size) // initializing boolean array with true values
{
for (int i = 2; i < size; ++i)
{
boolArr[i] = true;
}
return chickIfIndexPrime(boolArr, boolArr.length,size);
}
public static boolean[] chickIfIndexPrime(boolean[] arrIsPrime, int input, int size)
{
int start = 2;
while (start*start <= input) // first+second loop checking if start is prime
{
int i = 2;
boolean isprime = true;
while(i*i < start && isprime ) // second loop
{
if(start%i == 0)
{
isprime = false;
}
++i;
}
if(isprime==true)
{
for(int j=4; j<arrIsPrime.length;++j) // third loop checking if the index of the array is prime
{
if(j%start ==0 )
{
if(j == start)
{
++j;
if(j >=arrIsPrime.length)
{
break;
}
}
arrIsPrime[j]=false;
}
}
}
++start;
}
return arrIsPrime;
}
public static void printArray(boolean[] arr ,int size){
System.out.println("The prime numbers from 2 till "+(size));
int i=0,j = 0 ;
while(i<arr.length){
if ( arr[i] == true ) {
System.out.print(i+" ");
++counter;
}
++i;
}
System.out.println();
System.out.println("\nIn total there is "+counter+" prime numbers");
}
}
Mero
