-6

我需要代码来在不到 10 分钟的时间内确定第 1000000 个原始数。我已经写了下面的课程，但它没有我需要的那么快。如何优化这个类来提高它的计算速度？您可以通过调用get_thPrimitive(int number). 那将返回很长。

public class PrimitiveF
{
    // this is our class named PrimitiveF
    private static boolean isPrimitive(long n) 
    {
        //isPrimitive method is a private static method that is used in get_thPrimitive method
        //this method tells us if the number is primitive or not 
        long p=(long)Math.sqrt(n);//here we get square of the input number

        int i=2;
        while(i<=p)//now we check the nember is primitive or not if it is primitive we'll return true
        {
            int k=0;
            for(int j=2;j<=i;j++)
                if(i%j==0)
                    k++;
            if(k==1)
            {
                if(n%i == 0)
                    return false;
            }
            i++;
        }

        return true;
    }

    public static long get_thPrimitive(int n)//get_thPrimitive method is a public static //method
    {
        //this method would give us the Xth primitive number
        int count=0,i=2;
        while(count < n)
        {
            if(isPrimitive(i))
                count++;
            i++;
        }

        return --i;
    }
}
4

2 回答 2

2

当且仅当 n 没有素数除数时，您从该 isPrimitive() 方法返回 false。为此，您生成所有素数，直到 sqrt(n)...但是您使用许多内部素数测试只是为了执行一个更大的测试，并且您对这些内部素数测试使用了一种缓慢的方法。

如果代码是正确的，但速度太慢，那么您可以通过以下方式获得巨大的加速：

  1. 如果 n 是偶数，则如果 n 为 2，则返回 true，否则对于任何其他偶数返回 false。
  2. 在您的循环中，仅测试从 3 开始且小于或等于 sqrt(n)+1 的奇数除数。不要担心这些是否是主要除数。没关系，测试除数的素数只会减慢你的速度。

如果 n 是奇数并且上面没有检测到奇数除数，则它是素数。

这将大大加快您的代码速度。如果这还不够快，您可以使用 Sieve 算法进行调查。基本方法源于古代的埃拉托色尼（Eratosthenes），在维基百科中有描述

于 2013-11-02T10:34:18.123 回答
2

如果原始的意思是素数（我已经看到可以互换使用的术语），那么您使用的是最慢的算法之一。搜索“筛子”，也许是“二次筛子”以获得更快的解决方案。

编辑：哦，对于筛子，您需要一个大小为 16,000,000 的数组（第 100 万个素数略低于 15.5M）。

于 2013-11-02T10:40:47.867 回答