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

本文介绍了为什么要乘以比服用平方根快很多倍？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我有几个问题与下面的算法来判断一个数是素的，我也知道，随着筛埃拉托色尼的可以更快的响应。

I have several questions with the following algorithms to tell if a number is prime, I also know that with the sieve of Eratosthenes can be faster response.

为什么要快，计算 II * SQRT（N）次。比的sqrt（N）只是一个时间？
为什么的Math.sqrt（）比我的 SQRT更快的（）的方法？
什么是这些算法为O（n），O（开方（N）），O（N日志（N））？复杂

Why is faster to compute i i * sqrt (n) times. than sqrt (n) just one time ?
Why Math.sqrt() is faster than my sqrt() method ?
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;
}
}

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

This is the link of my code also: http://ideone.com/Fapj1P

sqrt

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

问题描述

推荐答案