Java: создание больших случайных чисел

Я создал простую программу простой факторизации на java для удовольствия. Прямо сейчас я использую класс Random и метод nextLong(), чтобы присвоить «temp» случайное число в диапазоне квинтиллионов и удивительно быстро факторизовать его. Какой тип данных, алгоритм или метод следует использовать для получения значительно больших значений?

import java.util.Random;
import javax.swing.JOptionPane;

public class factor {
public static void main(String[] args) {
   Random gen = new Random();
   String factors = "";
   long temp = 0;
   String hello = JOptionPane.showInputDialog("Type a random number(Must be smaller than 4,611,686,018,427,387,904), or type 1 for a random large number.");
  temp = Long.parseLong(hello);
   if(temp < 2)
   temp = Math.abs(gen.nextLong());
   long temp2 = temp;
   System.out.println("  The factors of   \n\n  " + temp2 + "   are:");
   System.out.println("");
   while(temp != 1){
       //System.out.print(temp);
   for(long ii = 2; ii <= (Math.ceil(Math.sqrt(temp))); ii++){
  // if(ii%12345 == 0)
 // System.out.println(temp + " " + ii + " " + factors);
        if(temp%ii == 0){
            factors = factors + "  " + ii;
           // System.out.println(temp + " " + ii + " " + factors);
            temp = temp/ii;
            ii = temp + 1;       
  }else{
   if(ii == Math.ceil(Math.sqrt(temp))){
   factors = factors + " " + temp;
            System.out.println(factors);
            temp = 1;
            ii = temp + 1;   
   }}
        }
   }}}

person sgrutman978    schedule 29.04.2014    source источник
comment
Если бы вы использовали квантовый компьютер, вы все равно не смогли бы получить наибольшее случайное число.   -  person yitzih    schedule 30.04.2014
comment
Он факторует это быстро, потому что это неправильно. Я не уверен, что вы понимаете, что делаете в этом коде. if(temp%ii == 0) тогда... ii = temp +1 Почему? Какой результат вы получите, например, для числа 81? Вы получаете 3 3 3 3 ?   -  person peter.petrov    schedule 30.04.2014
comment
BigInteger приходит на ум...   -  person takendarkk    schedule 30.04.2014
comment
Я не понимаю вопроса, нет самого большого случайного числа. Вы имеете в виду самый большой, который поместится в двухместный? Или самое большое, что может быть представлено компьютером или .....? (BigInterger имеет ограничения по размеру только в зависимости от доступной памяти)   -  person Richard Tingle    schedule 30.04.2014
comment
попробуй запустить с вводом 81 питер, все заработает. Я разложил на множители такие числа, как 5684275247958, за несколько секунд и снова перемножил простые множители, и это сработало.   -  person sgrutman978    schedule 30.04.2014
comment
Хорошо, я посмотрю, вы меня заинтересовали :)   -  person peter.petrov    schedule 30.04.2014
comment
Хорошо, я беру это обратно. Извиняюсь.   -  person peter.petrov    schedule 30.04.2014
comment
Ха-ха :) Извинения приняты. Да, моя цель в этом вопросе - я хочу иметь возможность учитывать большие числа, чем квинтиллионы. Поскольку Long может содержать только 2 ^ 63, потому что это 64-битный тип данных, так как я могу получить большие значения? Takendarkk, я думал об использовании BigInteger, но как мне сгенерировать случайный BigInteger?   -  person sgrutman978    schedule 30.04.2014
comment
Я попробую еще, позвольте мне найти вам несколько плохих примеров.   -  person peter.petrov    schedule 30.04.2014
comment
Попробуйте запустить на этом примере: temp = 4611686018427387903L; Это не так быстро, как вы думаете.   -  person peter.petrov    schedule 30.04.2014
comment
Попробуйте также: temp = 924961025514621481L.   -  person peter.petrov    schedule 30.04.2014
comment
4611686018427387903 потребовалось 20 секунд, чтобы сосчитать на моем компьютере. Я бы сказал, что это довольно хорошо, учитывая, что у него 3 ОГРОМНЫХ простых множителя и 19 цифр. Я сделал около 200 тестов, средняя скорость составила около 5 секунд для случайных чисел с более чем 17 цифрами.   -  person sgrutman978    schedule 30.04.2014
comment
Ну, если вы думаете, что это хорошо ;) Я думаю, что это не так. Я думаю, есть лучшие способы. Это довольно простой алгоритм, который вы реализовали. Попробуйте также 5075762304003453001 и 4591670831448457501.   -  person peter.petrov    schedule 30.04.2014
comment
Не чините то, что не сломано. Но из любопытства, какой алгоритм был бы более эффективным?   -  person sgrutman978    schedule 30.04.2014
comment
en.wikipedia.org/wiki/Primality_test   -  person peter.petrov    schedule 30.04.2014
comment
en.wikipedia.org/wiki/Integer_factorization   -  person peter.petrov    schedule 30.04.2014
comment
en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorization   -  person peter.petrov    schedule 30.04.2014
comment
alpertron.com.ar/ECM.HTM   -  person peter.petrov    schedule 30.04.2014
comment
Это хороший документ с описанием нескольких методов факторизации: connellybarnes.com/documents/factoring.pdf   -  person Barry Brown    schedule 30.04.2014


Ответы (2)


Вы можете использовать случайный конструктор для BigInteger:

BigInteger(int numBits, Random rnd)

Если вам нужна дополнительная информация, вы можете проверить API: Большоецелое

person RyNo    schedule 29.04.2014

Это бесполезно и, к сожалению, закодировано. Вы можете играть с большими числами и говорить, что это быстро, но дело не в том, «насколько велико мое число»… а в том, «насколько велики множители». Просто возьмите большое простое число и спите, пока ваш код не заработает.

Для генерации больших чисел... есть BigInteger

public class Factor {

    public static BigInteger generateBigOne() {
        final Random random = new Random();

        long loop = random.nextLong();
        String result = "";
        for (int i = 0; i < loop; i++) {
            result += random.nextLong();
        }
        return new BigInteger(result);
    }
}
person farvilain    schedule 29.04.2014