/*

Решето на Ератостен 
 
Алгоритъмът работи сравнително добре за малки числа, 
но при по-големите има значителен преразход на памет. 

В оригиналното решение подреждаме всички числа от 1 до n 
по-големина и започваме да ограждаме простите и да зачеркваме всички кратни на тях. 
Тъй-като 2 е просто можем да го отбележим като такова и 
да изключим всички четни числа от решетото още в началото, 
по този начин спестяваме половината памет и половината обхождане по вече зачертани числа. 
Това се получава с лека модификация на оригиналния алгоритъм. 

*/

// Nakov implementation

public class Solution {
	
	static void sieveOfEratosthenes(int n) {
		int sieve[] = new int[n+1];
		int i = 2, j = 0;
		
		while (i <= n) {
			if (sieve[i] == 0) {
				System.out.print(i + " ");
				j = i * i;
				while (j <= n) {
					sieve[j] = 1;
					j += i;
				}
			}
			++i;
		}
	}
	
	
	public static void main(String[] args) {
		sieveOfEratosthenes(199);
	}
}

Create 29092016-4.java