java - 如何减少Java程序的执行时间？

Question

我已经完成了这段代码，但似乎需要比允许的时间更长的时间 代码是生成多个两个数之间的素数。

这是代码:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.sql.Time;
import java.util.ArrayList;

public class App {

    public static boolean isPrime(int p) {
        int i;
        boolean t = false;

        if (p == 2) {
            t = true;
        } else {
            for (i = 2; i < p; i++) {
                if (p % i == 0) {
                    t = false;
                    break;
                } else {
                    t = true;
                }
            }
        }
        return t;
    }

    public static void numOfPrimes(int a, int b) {

        if (a >= 1 && a <= b && b <= 1000000000 && (b - a) <= 100000) {
            int i, prim = 0;
            boolean t = false;

            for (i = a; i <= b; i++) {
                t = isPrime(i);

                if (t) {
                    System.out.println(i + "\n");
                    prim++;
                }
            }
        } else {
            System.out.println("bad input!!");
            System.out.println("inputs must be just like (1 <= m <= n <= 1000000000, n-m<=100000) ");
        }
    }

    public static void main(String[] args) throws IOException, NumberFormatException {

        long t1 = System.currentTimeMillis();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = 0, counter = 0;
        String str;

        try {
            str = br.readLine();
            t = Integer.parseInt(str);
            ArrayList<String> arr = new ArrayList<String>();

            while (counter < t) {
                String s = br.readLine();
                arr.add(s);
                counter++;
                System.out.println("\n");
            }

            for (int x = 0; x < arr.size(); x++) {
                StringBuffer s1 = new StringBuffer(" "), s2 = new StringBuffer("");
                int q = 0, i, j;
                int num1, num2;

                for (i = 0; i < arr.get(x).indexOf(' '); i++) {
                    q++;
                    s1 = s1.append(arr.get(x).charAt(i));
                }

                String s5 = s1.toString();

                for (j = q + 1; j < arr.get(x).length(); j++) {
                    s2 = s2.append(arr.get(x).charAt(j));
                }

                String s6 = s2.toString();

                try {
                    num1 = Integer.parseInt(s5.trim());
                    num2 = Integer.parseInt(s6.trim());
                    App.numOfPrimes(num1, num2);
                    System.out.println("\n");
                } catch (NumberFormatException e) {

               //Will Throw exception!
               //do something! anything to handle the exception.
                }
            }
        } catch (Exception ex) {
            System.out.println("IO error ");
            System.exit(1);
        }

        long t4 = System.currentTimeMillis();
        System.out.println(t4 - t1);
    }
}

Answer 1

您在这里使用了错误的算法。查看Sieve of Erasthothenes ，然后根据您的需要进行修改。此外，您想要找到 1 到 1x10^9 之间的质数，这相当多。也许您需要详细说明为什么需要这个。

编辑:

作弊方式:把http://compoasso.free.fr/primelistweb/page/prime/liste_online_en.php中的数字删掉而不是生成它。