Błąd z "OutOfMemoryError"

Witam.
Mam za zadanie napisać program w Javie, który tworzy sito Eratostenesa dla podanych liczb i wypisuje czy jest pierwsza, czy złożona.
Ewentualnie wyrzuca wyjątek, że nieprawidłowy format itd.
Mam problem z wyjątkiem OutOfMemoryError, ponieważ przy wpisywaniu np. liczby 999999999 działa on prawidłowo, ale przy podaniu argumentu 9999999999 wyskakuje "Brak liczb pierwszych i/lub zlozonych"
Proszę o pomoc i podsunięcie pomysłu co może być nie tak.
Z góry dziękuję.

Klasa SitoEratostenesa

//tworzenie Sita Eratostenesa
class MyException1 extends Exception {};

public class SitoEratostenesa {
	private static int n; 
	private static boolean[] tab;

	SitoEratostenesa(int n) {
		this.n = n;
		tab = new boolean[n + 1];
		
		for (int i = 2; i * i <= n; i++) {
			if (tab[i] == true)
				continue;
			for (int j = 2 * i; j <= n; j += i)
				tab[j] = true;
		}
	}

	// metoda sprawdzająca czy liczbą jest pierwsza
	// na utworzonym sicie
	public static boolean prime(int m) throws MyException1 {
		if (m > n)
			throw new MyException1();
		if (m < 2)
			throw new MyException1();
		return (!tab[m]);
	}
}
 

Klasa SitoEratostenesaTest

class MyException2 extends Exception {
};

public class SitoEratostenesaTest {
	public static void main(String[] args) {

		int maxArg;

		try {
			maxArg = SitoEratostenesaTest.maksimum(args);
		} catch (MyException2 ex) {
			//if (args.length == 0)
				System.out.println("Brak liczb pierwszych/ zlozonych");
			return;	
		}
	

		try {
			SitoEratostenesa Sito = new SitoEratostenesa(maxArg);
			for (int i = 0; i < args.length; i++) {
				try {
					Integer.parseInt(args[i]);
					
				} catch (NumberFormatException err) {
					System.out.println("\"" + args[i] + "\" nieprawidlowy argument.");
					continue;
				}
				try {
					if (Sito.prime(Integer.parseInt(args[i])))
						System.out.println(args[i] + " jest liczba pierwsza.");
					else
						System.out.println(args[i] + " nie jest liczba pierwsza.");
					
				} catch (MyException1 e) {
					System.out.println(args[i] + " to liczba ponizej zakresu (ponizej 2).");
					continue;
				}
			}
		} catch (OutOfMemoryError err) {
			System.out.println("Proba utworzenia za duzego sita!");
			return;
		}
	}

	public static int maksimum(String args[]) throws MyException2 {
		int max = 0;
		int h = 0;

		for (int i = 0; i < args.length; i++) {
			try {
				h = Integer.parseInt(args[i]);
			} catch (NumberFormatException ex) {
				continue;
			}
			if (h > max)
				max = h;
		}
		if (max < 2)
			throw new MyException2();
		return max;
	}
}

Treść zadania: http://mgc.im.pwr.wroc.pl/dyd/kp2013/lista02.pdf

Ech, szkoda słów.

tab = new boolean[n + 1];

9999999999 * 1 bajt = 9,3GB, masz tyle ramu żeby zaalokować taką tablicę booleanów?

Shalom napisał(a):

Ech, szkoda słów.

tab = new boolean[n + 1];

9999999999 * 1 bajt = 9,3GB, masz tyle ramu żeby zaalokować taką tablicę booleanów?

Problem jest własnie w tym, że OOME nie jest rzucane...

...gdyż, ponieważ, aczkolwiek...

9999999999 nie mieści się w zakresie inta.

Dodatkowo podpowiem, że indeksy tablic są intami, więc tablica może mieć rozmiar maksymalnie 2^31 - 1 elementów (np double'i, co da tablicę na 16 GiB).

Do implementacji sita Erastostenesa wprost stworzona jest klasa BitSet, której indeksy odpowiadają wartościom liczbowym, a odpowiedź o tym czy liczba jest pierwsza zawarta jest w jednym bicie. Do tego można jeszcze dodać jej wrappera tak aby indeksy dotyczyły tylko liczb nieparzystych bo parzyste nie są pierwsze z definicji. W ten sposób całe sito dla liczby 9999999999 zmieści się w obiekcie BitSet o wielkości mniejszej niż 600 MB. I to wystarczy. Do zaimplementowania jedynie iteracja skreślania po tak skonstruowanym sicie.

ps. Kiedyś wrzuciłem nawet działającą prostą implementacją bez wrappera: http://4programmers.net/Forum/Java/186553-liczby_pierwsze_-_java

A czy przypadkiem boolean to nie jest 1/8 bajta(oktetu)? (1 bit)
1.1625 Gb, to aż tak dużo nie jest.
Oczywiście mogę się mylić (co będzie świadczyć o zachłanności javy ;p)

Czy wyjątek "java.lang.OutOfMemoryError: Java heap space" dotyczy tylko braku miejsca w pamięci RAM ? U mnie jest tak

Program uruchomiony, ale bez alokacja tab; 1,64 GB

tab = new boolean[ 399 999 999 ]; 2,02 GB
tab = new boolean[ 699 999 999 ]; 2,29 GB
tab = new boolean[ 799 999 999 ]; Exception in thread "AWT-EventQueue-0" java.lang.OutOfMemoryError: Java heap space

Program za każdym razem był uruchamiany z inną wielkością tab. Wyjątek ten wyskakuje mi pomimo tego że mam jeszcze 1,5 GB wolnego miejsca w pamięci RAM, a nie sądzę żeby skok o 100 mln pochłoną nagle tyle pamięci skoro wcześniej pomimo zwiększenia o 300 mln zżarł tylko 270 mb.

722:
Standardowo sterta w Javie podzielona jest na pewne części, np Eden, Survivor1, Survivor2, OldGen, PermGen, itd związane jest to z działaniem domyślnego GC. Każdy obiekt musi się zmieścić w całości w którymś z tych obszarów, a ich rozmiary nie są do końca elastyczne, tzn nie wszystkie rozciągają/ kurczą się po uruchomieniu JVM. Możliwe, że w G1 GC nie występuje ten problem, bo tam nie ma stricte podziału sterty na generacje.

I wszystko jasne ! Dziękuję za odpowiedz :)

@722 a odpaliłeś JVM z parametrami -Xmx? Daj sobie -Xmx4g i wtedy JVM będzie mógł zjeść 4GB

Do tej pory odpadłym bez żadnych parametrów i faktycznie z parametrem -Xmx4g program może zużyć więcej pamięć. Dzięki za pomoc.