在 for 循环中使用哪个更有效，i<sqrt(n) 或 i*i<(n)？

Question

谁能帮我看看下面这两个哪个更有效更正确？

1.

for(int i = num; i * i <= n; i++)

2.

int root = sqrt(n);
for(int i = num; i <= root; i++)

在第一种方法中，我们在每次循环运行时计算 i 的平方。此外，我们无法预先计算 i 的平方，因为 i 每次都会更新。

在第二种方法中，我们不是每次都计算 sqrt(n)。这是节省时间吗？

即使对于大数字（如 10^6），第二个循环是否会更快地获得 100% 准确的结果？

Answer 1

第二种情况应该更有效是有道理的，因为不需要为循环中的每次迭代计算循环限制器。尝试使用下面给出的代码测量通过 2 种类型的 for 循环所用的 CPU 时间。看起来 cpu 时间实际上对于第一种情况更小，对于较小的数字，如 n=25。但是对于 n>=100 的值，第二种情况给出了更短的 cpu 时间。

    clock_t start,end;
    double cpu_time_used;
    double n, root;

    n = atoi(argv[1]);
    printf("n= %0f \n",n);
    start = clock();
    for (int i=0; i*i<n; i++);
    end = clock();
    cpu_time_used = ((double) (end-start)) / CLOCKS_PER_SEC;
    printf("first iter: cpu_time_used: %f \n", cpu_time_used);

    start = clock();
    root = sqrt(n);
    for (int i=0; i<=root; i++);
    end = clock();
    cpu_time_used = ((double) (end-start)) / CLOCKS_PER_SEC;
    printf("second iter: cpu_time_used: %f \n", cpu_time_used);

输出：

n= 25.000000 
first iter: cpu_time_used: 0.000004 
second iter: cpu_time_used: 0.000011 

n= 100.000000 
first iter: cpu_time_used: 0.000002 
second iter: cpu_time_used: 0.000001 

n= 1000000.000000 
first iter: cpu_time_used: 0.000011 
second iter: cpu_time_used: 0.000008

在 for 循环中使用哪个更有效，i<sqrt(n) 或 i*i<(n)？

Which is more efficient to use in a for loop, i<sqrt(n) or i*i<(n)?

c

time-complexity

square

primality-test

c++14