0

我在 Java 中完成了一项家庭作业，以创建查找素数等的类（您会在代码中看到更好的内容）。

我的代码：

    class Primes {

    public static boolean IsPrime(long num) {
        if (num%2==0){
            return false;
        }

        for (int i=3; i*i<=num;i+=2) {
            if (num%i==0) {
                return false;    
            }
        }
        return true;
    }   //  End boolen IsPrime

    public static int[] primes(int min, int max){
        int counter=0;
        int arcount=0;

        for (int i=min;i<max;i++){
            if (IsPrime(i)){
                counter++;
            }   
        }

        int [] arr= new int[counter];
        for (int i=min;i<max;i++){
            if (IsPrime(i)){
                arr[arcount]=i;
                arcount++;
            }               
        }
        return arr;
    }   //  End Primes

    public static String tostring (int [] arr){
        String ans="";
        for (int i=0; i<arr.length;i++){
            ans= ans+arr[i]+ " ";
        }
        return ans;
    }

    public static int closestPrime(long num){
        long e = 0 , d = 0 , f = num;
        for (int i = 2; i <= num + 1 ; i++){
            if ((num + 1) % i == 0){
                if ((num + 1) % i == 0 && (num + 1) == i){
                    d = num + 1;
                    break;
                }
                num++;
                i = 1;
            }
        }
        num = f;
        for (int i = 2; i < num; i++){
            if ((num - 1) % i == 0){
                if ((num - 1) % i == 0 && (num - 1) == i){
                    e = num - 1;
                    break;
                }
                num--;
                i = 1;
            }
        }
        num = f;
        if (d - num < num - e) System.out.println("Closest Prime: "+d);
        else System.out.println("Closest Prime: "+e);

        return (int) num;
    }   //  End closestPrime

}//end class

我的代码的目标是更快（和正确）。我很难做到这一点。建议？

**新代码：

class Primes {

     public static boolean IsPrime(int num) {

         if (num==1){
             return false;
         }
         for (int i=2; i<Math.sqrt(num);i++) {
             if (num%i==0) {
                 return false;
             }
         }
         return true;
     }
          //  End boolen IsPrime

     public static int[] primes(int min, int max){
         int size=0;
         int [] arrtemp= new int[max-min];

         for (int i=min;i<max;i++){
             if (IsPrime(i)){
                 arrtemp[size]=i;
                 size++;
             }   
         }

         int [] arr= new int[size];
         for (int i=0;i<size;i++){
                arr[i]=arrtemp[i];

             } 
         return arr;

     }  

    public static String tostring (int [] arr){
        String ans="";
        for (int i=0; i<arr.length;i++){
            ans= ans+arr[i]+ " ";
        }
        return ans;
    }

    public static int closestPrime(int num) {
        int count=1;    
        for (int i=num;;i++){

            int plus=num+count, minus=num-count;
            if (IsPrime(minus)){

                return minus;

            }

            if (IsPrime(plus)) {
                return plus;

            }
            count=count+1;
        }
    }   //  End closestPrime

}//end class

我确实试图让它变得更好一点。你觉得呢，它可以进一步改进吗？（速度测试还是很高的……）

4

3 回答 3

1

在您的primes功能中，您：

  • 检查当前数是否能被二整除
  • 检查它是否是素数
  • 创建一个数组来放入你的输出。
  • 在将其放入数组之前，再次检查范围内的每个数字的素数。

问题出在最后一步。通过仔细检查每个数字是否为素数，您正在重复最昂贵的操作。

您可以使用动态数据结构并在找到它们时向其中添加质数。这样你只需要检查一次。

或者，您可以创建一个布尔数组，它是您的输入范围的大小。然后，当您找到素数时，将相应的数组值设置为 true。

更新：

您仍然可以进行许多改进，但有些改进需要比其他改进更多的工作来实施。查看您的测试细节，看看什么适合您的需求。

低垂的果实：

  • 使用 anArrayList收集在 中找到的素数primes，而不是循环两次。
  • 在closestPrime中，您正在检查 两侧的每一个值num：其中一半是偶数，因此不是素数。您可以调整代码以仅检查奇数的素数。

实施起来更棘手：

最重要的是，您应该花一些时间弄清楚代码中的瓶颈到底在哪里。通常，性能问题是由我们认为非常好的代码引起的。您可能会考虑查看您的开发环境中可用的代码分析选项。

于 2013-03-25T23:48:00.217 回答
0

我看到你的回答有几个问题。首先，2是质数。您在 IsPrime 中的第一个条件打破了这一点。其次，在您的素数方法中，您正在循环从最小值到最大值的所有数字。您可以放心地忽略所有负数和所有偶数（就像在 IsPrime 中所做的那样）。将这两种方法结合起来并节省所有额外的周期会更有意义。

于 2013-03-25T23:46:48.490 回答
0

您对 isPrime() 进行了多次调用，每个调用都非常昂贵。您的第一步应该是尽量减少这样做的次数，因为任何给定数字的结果都不会改变，因此多次调用是没有意义的。您可以通过在计算值后存储值来进行记忆：

ArrayList<Integer> memoList = new ArrayList<Integer>();
for(int i = 0; i < max; i++) {
  if(isPrime(i)) {
    memoList.add(i);
  }
}

现在 memoList 保存了所有你需要的素数，直到max，你可以快速循环它们，而无需每次都重新计算它们。

其次，你可以改进你的isPrime()方法。您的解决方案循环遍历从 3 到 sqrt(n) 的每个奇数，但是既然我们知道了质数，为什么不直接遍历质数呢？

public static boolean IsPrime(long num) {
    for(int p : memoList) {
        if(num % p == 0) {
            return false;
        }
    }
    return true;
}

这些更改应该会显着提高您的代码运行速度，但是已经有很多关于计算素数的更有效方法的研究。Prime Numbers的 Wikipedia 页面提供了一些关于您可以尝试的进一步策略（尤其是素数筛）的非常好的信息。

请记住，由于这是家庭作业，您应该确保在上交时引用此页面。欢迎您使用和扩展此代码，但不引用此问题和您使用的任何其他资源都是抄袭。

于 2013-03-25T23:45:39.430 回答