java - 如何在java中优化素数生成器？

Question

我在 SPOJ 上做了一些问题，它被称为素数生成器。

我的代码在本地计算机上运行良好，但在 SPOJ 上我收到超出时间限制的错误。

有人可以告诉我如何使这个程序和具有大量嵌套循环的类似程序更有效地运行吗？

  import java.util.*;
  import java.lang.*;
  import java.math.*;

  class Main {
     public static void main (String[] args) throws java.lang.Exception {
        Scanner obj = new Scanner(System.in);
        int t = obj.nextInt();

        for(int i = 0; i < t; i++) {
           int m = obj.nextInt();
           int n = obj.nextInt();

           for(int x = m; x <= n; x++) {
              boolean flag = true;
              int count = 0;
              for(int j = 2; j < Math.pow(n,0.5) ; j++) {
                 if(x == 1 || x == 2) {
                    flag = false;
                    break;
                 }
                 if(x % j == 0 && x != j) {
                    flag = false;
                    break;
              }
           }
           if(flag) {
              System.out.println(x);
           }
        }
        System.out.println();
     }
  }

Answer 1

• 每次在循环中调用 Math.pow(n,0.5) 应该会很慢，因此应该在每个循环之前调用一次并保存返回值。
• 您只需将这些值除以等于或小于 sqrt(n) 的质数。
• 使用埃拉托色尼筛之类的东西。不要单独判断每个数字，而是从数字列表中删除素数的倍数。