Wyszukiwanie liczb pierwszych BigInteger

0

Witam,

Potrzebuję dla spraw związanych z kryptografią, wyszukać dużych liczb pierwszych, poczytałem o klasie BigInteger, jednakże, obliczenia te są dość czasochłonne i w efekcie dostaję błędy o przekroczeniu pamięci. Jak można zoptymalizować ten kod?

package logika;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

public class LiczbyPierwsze {

	/**
	 * @param args
	 */

	List<BigInteger> lista;

	public void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println("Hello");
		lista = new ArrayList<BigInteger>();
		BigInteger n = new BigInteger("1208925819614629174706175");
		BigInteger m = new BigInteger("1");
		while (m.compareTo(n) < 0) {
			if (m.isProbablePrime(20)) {
				lista.add(m);
			}
			m = m.add(BigInteger.ONE);
		}
	}

	public List<BigInteger> getLista() {
		return lista;
	}
}

Chciałbym, by to były dość dobre podwaliny pod przyszłą rozbudowę, czyli wyszukanie, na ile dana liczba z tego przedziału (liczba 80 bitowa) sposobów może być wynikiem mnożenia różnych liczb pierwszych, by określić przedziały gdzie jest najwyższy poziom "bezpieczeństwa".

0

liczba jest liczbą pierwszą jeżeli żadna z liczba pierwszych mniejsza od jej połowy, nie jest dzielnikiem tej liczby.
Kiedyś było takie zadanko w OPSS, pierwsze 15000 liczb pierwszych w Javie wyszukiwało się ~1,5 sekundy zgodnie z powyższym zdaniem.

0
  1. Skąd wiesz, że kod jest czasochłonny? Przecież tego programu nie uruchomisz.
  2. Jaki jest związek czasochłonności z brakiem pamięci?
0
  1. Uruchamia się, to jest po prostu klasa spoza pakietu gdzie kod "startuje"
  2. To fakt, jednak wolałbym by program wygenerował wszystkie liczby pierwsze od liczb 0 bitowych do 80 bitowych, a nie przestawał działać w nieokreślonym momencie, bo pamięć javy została przepełniona.
0

To zwiększ pamięć dla JVM. Wpisz w konsoli java -X, to się dowiesz jak to zrobić.

0

To akurat wiem, miałem nadzieję na lepszy sposób, bo program na prawdę długo się wykonuje, a jak do tego jeszcze dojdzie mnożenie tych liczb to może problem się powtórzyć.

2

tych liczb jest jakieś 2*10^22
powiedzmy miliard na sekundę
to będzie 60 czy 600 tysięcy lat?

0

Właśnie tego się obawiałem. Mógłbym wiedzieć, na jakiej podstawie szacujesz ile będzie liczb pierwszych w tym przedziale?

2

Ilość liczb pierwszych w przedziale [1,n] wynosi w przybliżeniu n/ln(n). 1000 000 000 000 000 000 000 000<1208 925 819 614 629 174 706 175<10 000 000 000 000 000 000 000 000 =>
24 = log(1000000000000000000000000)<log(1208925819614629174706175)<log(10000000000000000000000000)=25. Zatem
1208925819614629174706175/25 < 1208925819614629174706175/log(1208925819614629174706175) < 1208925819614629174706175/24.

0

Dziękuję bardzo za pomoc. Jak dla mnie temat jest wyczerpany.

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