为什么要乘以比服用平方根快很多倍？

什么是这些算法为O（n），O（开方（N）），O（N日志（N））？复杂

What is the complexity of these algorithms 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; } }