如何让此代码适用于BigIntegers？此代码是关于查找数字（n）的最大素数因子

-4

public class E2 { 

    public static void main(String[] args) { 
     long i,f,n=12345,p=1,j; 
     for(i=2;i<n;i++) 
     { 
      if(n%i==0) 
      { 
       f=i; 
       for(j=2;j<=f/2;j++) 
       { 
        if(f%j==0) 
         break; 
        else 
         continue; 
       }j--; 
       if(j==f/2) 
        p=f; 
      } 
      else 
      {continue;} 
     } 
     System.out.println(p); 
    } 
}

这里，n是一个随机数，其最大质数要查找。代码适用于很长的整数。我首先应用一个for循环来找到一个因子n，并检查该因子是否为素数，如果它们是素数，则它们存储在p中，因此p的最后一个值是最大的素数因子。如何让此代码适用于BigIntegers？此代码是关于查找数字（n）的最大素数因子

来源

2016-01-23 Shubham

您是否尝试过使用'BigInteger'？如果是，你失败了？您是否阅读过[JavaDoc]（https://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html）？ – Tom

是的，我试过BigInteger，当我需要在循环（重复）中分割并找到BifInteger的mod时，我被卡住了。 – Shubham

这种方法效率很低，如果您需要处理更大的数字，那么长时间不适合，您还需要使用更好的算法。

以下程序仍然只适用于long，但效率更高。然而，它仍然不足以超越long的范围。请注意，对于您添加的每两位数字，最差情况下的运行时间将增加10倍。

将给定测试用例的运行时间与您的方法进行比较。或者如果你不想等这么长时间，可以拿一些较小的数字，如1234567890L。

它通过划分较小的素数因子来工作，并且因此避免了需要检查发现的因素是否为素数，因为之前已经发现了较小的因子。

经过检查高达sqrt（n）的因素后，剩余的未分割片n必须是素数（或1）。这是因为否则其中一个主要因素必须小于或等于sqrt（n），因此以前会发现它。

实际上，只用质数进行试用分区就足够了，但由于我们没有列表，所以在这里采取的折衷办法是将2作为特例，然后只尝试奇数。与简单版本相比，该算法加快了算法的2倍。

public class Main { 

    public static void main(String[] args) { 
     long n = 123456789L; 
     System.out.printf("largest prime factor of %d is %d%n", n, largestPrimeFactorOf(n)); 
     n = 123456789L; 
     System.out.printf("largest prime factor of %d is %d%n", n, largestPrimeFactorOf(n)); 
     n = 123456789L; 
     System.out.printf("largest prime factor of %d is %d%n", n, largestPrimeFactorOf(n)); 
     n = 123456789L; 
     System.out.printf("largest prime factor of %d is %d%n", n, largestPrimeFactorOf(n)); 
     n = 4611686014132420609L; 
     System.out.printf("largest prime factor of %d is %d%n", n, largestPrimeFactorOf(n)); 
    } 

    public static long largestPrimeFactorOf(long n) { 
     long last = 1; 
     while (n % 2 == 0) { 
      System.out.printf("prime factor 2 found%n"); 
      n /= 2; 
      last = 2; 
     } 
     for (long t = 3; t * t <= n; t += 2) { 
      while (n % t == 0) { 
       System.out.printf("prime factor %d found%n", t); 
       n /= t; 
       last = t; 
      } 
     } 
     return n == 1 ? last : n; 
    } 
}

这个程序的输出是

prime factor 3 found 
prime factor 3 found 
prime factor 101 found 
prime factor 3541 found 
prime factor 3607 found 
prime factor 3803 found 
largest prime factor of 123456789is 27961 
prime factor 7 found 
prime factor 164005957 found 
largest prime factor of 123456789is 1075368509 
prime factor 38429233 found 
largest prime factor of 123456789is 32125748909 
largest prime factor of 123456789is 123456789
prime factor 2147483647 found 
prime factor 2147483647 found 
largest prime factor of 4611686014132420609 is 2147483647

来源

2016-01-23 09:32:08 Henry

是的，这段代码真的很高效，感谢您的帮助！ – Shubham

对于完全不同的问题，这是一个很好的答案。 –

@DavidWallace在技术上是的，因为我觉得原来的问题是一个XY问题的实例http://meta.stackexchange.com/questions/66377/what-is-the-xy-problem，真正的问题是“如何可以我让它适用于更大的数字“ – Henry

如何让此代码适用于BigIntegers？此代码是关于查找数字（n）的最大素数因子

回答

相关问题