3

我是一名在大学学习 IT 的学生。我一直在分配寻找万亿以上素数的任务。已给出步骤：

  • 起始数字为一万亿

  • 选择奇数候选人

  • 将它们除以 3 和它们的平方根之间的每个奇数。如果其中一个整数均分候选者，则它被宣布为素数。

现在这就是我想出的：

import java.io.*;
import javax.servlet.*;
import javax.servlet.http.*;

public class PrimeSearcher extends HttpServlet{
    private long number = 10000000000000001L;
private boolean found = false;
public void doGet(HttpServletRequest request, HttpServletResponse response) throws IOException, ServletException {
    PrintWriter out = response.getWriter();

    while(!checkForPrime(number)){
        number = number+2;
    }

    if(found){
        out.println("The first prime number above 1 quadrillion is : " + number);
    }

}

public boolean checkForPrime(long numberToCheck){
    double sqrRoof = Math.sqrt(numberToCheck);
    for(int i=3; i< sqrRoof; i++){
        if(numberToCheck%i==0){
         return false;
        }
    }
    found= true;
    return found;
}


}

我担心的是不确定我是否走在正确的道路上，另一个问题是这总是一个数字，第一个。谷歌搜索后，我在servlet.com和javafaq上发现他们正在使用线程，我已经运行了他们的线程，看起来很酷。我不太明白那个，但它给出了不同的数字。

所以我现在对如何实现该算法感到困惑，我真的不想复制那个算法。也许在理解了他们的方法之后，我可以更好地编写这个算法。

谢谢

4

4 回答 4

1

此外，您需要checkForPrime直到i<=sqrRoof（sqrRoof 可以是整数）。

于 2012-08-23T08:44:12.540 回答
1

我认为它看起来不错，但您可能需要iincheckForPrime成为一种long类型。而且您不会增加i2（您只需要检查奇数除数）。

只是准备好这个需要很长时间.......

于 2012-08-23T08:10:37.983 回答
1

检查大素数的标准方法是使用埃拉托色尼筛法生成一个低素数列表，直到某个限制。使用该列表检查万亿范围内的奇数，以消除大多数非素数。

然后使用Miller-Rabin概率素数检验来检查剩余的大数是否真的是素数。如果您重复 MR 测试多达 64 次，那么您的硬件发生故障的可能性要比您无意中找到一个合数的可能性大得多。

对于大数，MR 测试比试除法要快得多。

于 2012-08-23T13:57:52.077 回答
1

你的源代码中有 10 万亿，而不是 1 万亿。只是让你知道。:)

如果您需要它们，千万亿以上的质数是：

37,91,159,187,223 ...

10 万亿以上：

61,69,79 ...
于 2012-08-23T10:16:46.323 回答