Java long的最大素数

问题描述

我试图找到大量最大的素数。 例如，如果该数字为573849284703，我的代码将如下所示：

public static void main(String[] args) {

    long number = 573849284703l;

    System.out.println(lgstprmfactor(number));

}

public static long lgstprmfactor(long number) {
    for (long i = 286924642352l; i > 0; i--) {
        if (number % i == 0 && isPrime(i) == true) {
            long answer = i;
            return answer;
        }
    }
    return 0;
}

public static boolean isPrime(long i) {
    for (long c = 2; c < i; c++) {
        if (i % c == 0)
            return false;
    }
    return true;
}

但是要花很多时间运行任何建议，以加快它的速度或总体上优化代码？

public static void main(String[] args)
 {
  long startTime = System.currentTimeMillis();
  System.out.println(largestprimefactor(573849284703l));
  long endTime = System.currentTimeMillis();
  System.out.println(endTime - startTime+" ms ");
 }

public static int largestprimefactor(long l)
{
    int i;
    long copyofinput = l;
    for(i=2;i<copyofinput;i++)
    {
        if(copyofinput%i==0){

            copyofinput/=i;
            i--;
        }
    }

    return i;
}

}

输出：66718903

688毫秒

这里的基本思想是：找到质数因子时将其删除，不要搜索高于剩余数的平方根，并跳过偶数（而不是2）。 我还添加了一些错误检查和其他修饰。

public static void main(String[] args)
{
    try {
        System.out.println(largestPrimeFactor(573849284703l));
    } catch (ArithmeticException e) {
        System.out.println("Error factoring number: " + e.getMessage());
    }
}

private static long sqrtint(long n) {
  return (long)Math.sqrt(n + 0.5);
}

public static int largestPrimeFactor(long n) throws ArithmeticException
{
    if (n < 2) throw new ArithmeticException(n + " < 2");
    while (n%2 == 0) n /= 2;
    if (n < 2) return 2;
    long i, root = sqrtint(n);
    for(i=3; i<root; i+=2)
    {
        if(n%i == 0) {
            n /= i;
            while (n%i==0) n /= i;
            if (n == 1) return i;
            root = sqrtint(n);
        }
    }

    return n;
}

}