Нахождение простого множителя длинного числа с использованием Java - PullRequest
Новая
       7

Нахождение простого множителя длинного числа с использованием Java

1 голос
/ 23 октября 2010 
public class prime
{
   public static void main(String[] args)
    {
     long thing = 600851475143L;
     for(long i = 300425737571L ; i == 0 ; i-- ){
     if (thing % i == 0)
     {
       long answer = i;
       System.out.println(answer);
       break;
     }
     }

    }

}

Это код, который у меня есть в настоящее время, однако я уже несколько минут запускаю его в DrJava, и он не дал результатов. Я предполагаю, что есть примерно миллион способов оптимизации моего кода; кто-нибудь сможет дать мне несколько советов?

Попытка решить несколько проблем программирования сегодня, и это вызывает у меня некоторые проблемы.

Большое спасибо:)

Ответы [ 3 ]

3 голосов
/ 23 октября 2010

Для вычисления простых факторов на не очень больших значениях было бы гораздо эффективнее генерировать простые числа с точностью до квадратного корня из "вещи", а затем пробовать их по одному.

Генерация простых чисел может быть сделана:

3 голосов
/ 23 октября 2010

Вам нужно только итерация до sqrt (вещь), однако.

И вообще, итерация будет быстрее, начиная с 2, так как половина чисел будет иметь коэффициент два (и 1 /3 с коэффициентом 3 и т. Д.

Вы также разбиваете только по первому фактору, поэтому пропустите все остальные 

 long thing = 600851475143L;
 for(long i = 0; i < 300425737571L ; i++ ){
     if (i * i > thing) {
       break;
     }
     if (thing % i == 0) {
       long answer = i;
       System.out.println(answer);
       break;
     }
 }
  • более сложные методы доступны, как говорит aioobe
2 голосов
/ 23 октября 2010

Нет, он сразу заканчивается, поскольку 

i == 0

не будет удерживаться на первой итерации.

Возможно, вы хотели написать что-то вроде этого: 

public class Test {
    public static void main(String[] args) {
        long thing = 600851475143L;
        for (long i = 16857 /* 300425737571L */; i > 0; i--) {
            if (thing % i == 0) {
                long answer = i;

                // Print the largest prime factor, then break loop (and quit)
                System.out.println(answer);
                break;
            }
        }
    }
}

Однако этот наивный метод факторизации крайне неэффективен.Поскольку факторизация 600851475143 равна 71 * 839 * 1471 * 6857, вам нужно будет выполнить итерации от 300425737571 до 6857 и выполнять каждый раз по модулю.Существует много не очень сложных методов, которые бы мгновенно решали факторизацию.

...