Duża tablica typu long[]

0

Witam,
mam za zadanie napisać program, w którym będzie tablica typu long, przechowująca najmniejsze dzielniki z kolejnych liczb (poza 0 i 1). Jeżeli dana liczba jest liczbą pierwszą, to dana wartość w tablicy jest zerem. Tablica ma wyglądać tak:

tab[0] = 0; // pomijamy
tab[1] = 0; // pomijamy
tab[2] = 0; // liczba pierwsza
tab[3] = 0; // liczba pierwsza
tab[4] = 2; // najmniejszy dzielnik 4 to 2
tab[5] = 0; // liczba pierwsza
tab[6] = 2; // najmniejszy dzielnik 6 to 2
tab[7] = 0; // liczba pierwsza
tab[8] = 2; // najmniejszy dzielnik 8 to 2
tab[9] = 3; // najmniejszy dzielnik 9 to 3
//    itd....

Aby zadeklarować taką tablicę robię:

long[] tab = new long[granica];

z tym, że górna granica tablicy też ma wartość long. Jednak jako id klucza w tablicy trzeba podawać jako Integer.
Może mi ktoś wyjaśnić jak to obejść?
Pozdrawiam

0

To masz problem, indeks w tablicy musi być typu int. W chwilach wolnych oblicz sobie rozmiar tablicy typu long[Long.MAX_VALUE].

1

Maks tablica może mieć ok 2 mld elementów (ograniczenie inta). Przy 8 bajtach na longa daje to ok 16 gigabajtów. Masz więcej pamięci?

1

Jak już wspomniano wątpliwe żebyś potrzebował indeksować longami, ale gdybyś jednak bardzo chciał to zamiast tablicy użyj sobie Map<Long,Long> i po kłopocie :P

1

Ponieważ tab[i] < i oraz i musi być intem (gdyż jest indeksem tablicy), więc nie ma potrzeby, aby tab było tablicą long[]. Wystarczy int[].

Jeżeli badałbyś liczby mniejsze niż 109, to ponieważ tab[i] <= sqrt(i), wystarczyłoby short[] zamiast int[] (sqrt(109) ~= 31622, a Short.MAX_VALUE = 32767).

1 użytkowników online, w tym zalogowanych: 0, gości: 1