哪些是更快的平方或根?

|
for (int i = 2; i * i <= n; i++)

for (int i = 2; i <= SQRT(n); i++)
我只是想知道哪种速度更快,所以我研究了一些原始算法来求根,对我来说,平方数会更快,但我不确定。这些循环用于确定数字“素数”。     
已邀请:
战友不应该介于两者之间
int sqrt = SQRT(n);
for (int i = 2; i <= sqrt; i++)
for (int i = 2; i * i <= n; i++)
答案将取决于您执行了多少次循环迭代。 sqrt方法每次迭代的工作量较少,但启动成本较高。请注意,这种过早优化的表情。     
编译器可能会“缓存” SQRT(n)的结果,但是i * i应该在每个步骤上进行计算。     
除非以硬件,查找或特殊的机器代码版本实现,否则平方根将花费更长的时间。牛顿迭代法是首选算法;它二次收敛。 最好为自己进行基准测试。我建议将调用移到循环外的平方根,这样您就只能执行一次,而不是每次检查退出条件时都执行一次。     
为什么不跳过它们并使用一些聪明的数学呢?以下代码避免使用第一个ѭ3First奇数之和始终是理想平方的属性。 我的旧博客文章的无耻插件(来自我死去的博客)
int isPrime(int n)
{
    int squares = 1;
    int odd = 3;

    if( ((n & 1) == 0) || (n < 9)) return (n == 2) || ((n > 1) && (n & 1));
    else
    {
        for( ;squares <= n; odd += 2)
        {
            if( n % odd == 0) 
                return 0;
            squares+=odd;
        }
        return 1;
    }
}
    
平方会更快。 但是,如果n大于最大int的平方根,则平方会溢出,然后比较会出错。平方根函数可以(并且您希望如此)以这样一种方式实现,即可以根据参数一直计算到最大可表示int。这意味着它不会以这种方式出错。 在Java中,最大的int是2 ^ 31-1,这意味着它的平方根刚好在46341下。如果您要查找大于此的素数,则平方会阻止您。     

要回复问题请先登录注册