为什么乘法比求平方根快很多倍？

我对以下算法有几个问题来判断一个数字是否是素数，我也知道随着埃拉托斯特尼筛法可以得到更快的响应。

1. 为什么计算速度更快i i * sqrt (n)次。比sqrt (n)就一次 ？
2. Why Math.sqrt()比我的快sqrt()方法 ？

3. 这些算法的复杂度分别是O(n)、O(sqrt(n))、O(n log(n))？

   public class Main {
   
   public static void main(String[] args) {
   
   // Case 1 comparing Algorithms
   long startTime = System.currentTimeMillis(); // Start Time
   for (int i = 2; i <= 100000; ++i) {
       if (isPrime1(i))
           continue;
   }
   long stopTime = System.currentTimeMillis(); // End Time
   System.out.printf("Duracion: %4d ms. while (i*i <= N) Algorithm\n",
           stopTime - startTime);
   
   // Case 2 comparing Algorithms
   startTime = System.currentTimeMillis();
   for (int i = 2; i <= 100000; ++i) {
       if (isPrime2(i))
           continue;
   }
   stopTime = System.currentTimeMillis();
   System.out.printf("Duracion: %4d ms. while (i <= sqrt(N)) Algorithm\n",
           stopTime - startTime);
   
   // Case 3 comparing Algorithms
   startTime = System.currentTimeMillis();
   for (int i = 2; i <= 100000; ++i) {
       if (isPrime3(i))
           continue;
   }
   stopTime = System.currentTimeMillis();
   System.out.printf(
             "Duracion: %4d ms. s = sqrt(N) while (i <= s) Algorithm\n",
             stopTime - startTime);
   
   // Case 4 comparing Algorithms
   startTime = System.currentTimeMillis();
   for (int i = 2; i <= 100000; ++i) {
       if (isPrime4(i))
           continue;
   }
   stopTime = System.currentTimeMillis();
   System.out.printf(
             "Duracion: %4d ms. s = Math.sqrt(N) while (i <= s) Algorithm\n",
             stopTime - startTime);
   }
   
   public static boolean isPrime1(int n) {
       for (long i = 2; i * i <= n; i++) {
           if (n % i == 0)
               return false;
       }
       return true;
   }
   
   public static boolean isPrime2(int n) {
       for (long i = 2; i <= sqrt(n); i++) {
           if (n % i == 0)
               return false;
       }
       return true;
   }
   
   public static boolean isPrime3(int n) {
       double s = sqrt(n);
       for (long i = 2; i <= s; i++) {
           if (n % i == 0)
               return false;
       }
       return true;
   }
   
   public static boolean isPrime4(int n) {
       // Proving wich if faster between my sqrt method or Java's sqrt
       double s = Math.sqrt(n);
       for (long i = 2; i <= s; i++) {
           if (n % i == 0)
               return false;
       }
       return true;
   }
   
   public static double abs(double n) {
       return n < 0 ? -n : n;
   }
   
   public static double sqrt(double n) {
       // Newton's method, from book Algorithms 4th edition by Robert Sedgwick
       // and Kevin Wayne
       if (n < 0)
           return Double.NaN;
   
       double err = 1e-15;
       double p = n;
   
       while (abs(p - n / p) > err * n)
           p = (p + n / p) / 2.0;
   
       return p;
   }
   }
   

这也是我的代码的链接：http://ideone.com/Fapj1P

1. Why is faster to compute i*i, sqrt (n) times. than sqrt (n) just one time ?看看下面的复杂性。计算平方根的额外成本。

2. Why Math.sqrt() is faster than my sqrt() method ?
Math.sqrt() 委托对 StrictMath.sqrt 的调用，这是在硬件或本机代码中完成的。

3. What is the complexity of these algorithms?
您描述的每个函数的复杂性

i=2 .. i*i<n O(平方(n))

i=2 .. sqrt(n) O(sqrt(n)*log(n))

i=2 .. sqrt (by Newton's method) O(sqrt(n)) + O(log(n))

i=2 .. sqrt (by Math.sqrt) O(平方(n))

牛顿法的复杂度为
http://en.citizendium.org/wiki/Newton%27s_method#Computational_complexity