时间戳

首页 > 解决方案 > 埃拉托色尼筛法的实现和比较

python-3.x - 埃拉托色尼筛法的实现和比较

问题描述

除了简单实现时间复杂度为 O(N log log N) 的埃拉托色尼筛法之外，我还尝试实现时间复杂度 O(N) 的修改。虽然，两者都产生了预期的结果，但不知何故，与下一个相比，前一个花费的时间要少得多，我无法弄清楚为什么。我真的很感激对此的一些指示。

实施1：

def build_sieve_eratosthenes(num):
    ## Creates sieve of size (num+1) to correct for 0-indexing.
    primes_sieve = [1] * (num+1)
    primes_sieve[0] = primes_sieve[1] = 0
    for p in range(2, num):
        if primes_sieve[p] == 1:
            for mul in range(2*p, num+1, p):
                primes_sieve[mul] = 0
    return primes_sieve

实施2：

def build_sieve_eratosthenes_linear(num):
    ## Creates sieve of size (num+1) to correct for 0-indexing.
    primes_sieve = [1] * (num+1)
    primes_sieve[0] = primes_sieve[1] = 0

    ## Builds a list of size (num+1) recording the smallest prime factor of each number.
    SPF = [1] * (num+1)

    ## Builds a list of all primes seen so far with pos indicator of position where to insert the next prime.
    ## Uses a large fixed memory allocation scheme to avoid the usage of append list operation.
    primes = [0] * num
    pos = 0

    for p in range(2, num+1):
        if primes_sieve[p] == 1:
            primes[pos] = p
            pos = pos + 1
            ## Smallest prime factor of a prime is a prime itself.
            SPF[p] = p
        for i in range(0, pos):
            if p * primes[i] <= num and primes[i] <= SPF[p]:
                primes_sieve[p*primes[i]] = 0
                SPF[p * primes[i]] = primes[i]
            else:
                break
    return primes_sieve

test_num = 2000000

测试方法

def find_sum_of_primes_upto_num_with_sieve(sieve, num):
    primes_sieve = sieve(num)
    primes_sum = 0
    for n in range(len(primes_sieve)):
        if primes_sieve[n] == 1:
            primes_sum = primes_sum + n
    return primes_sum

结果：

start2 = time.time()
sum_2 = find_sum_of_primes_upto_num_with_sieve(build_sieve_eratosthenes, test_num)
end2 = time.time()
print("Sum of primes obtained: ", sum_2)
print("Time taken by checking primality of each number is %f sec" % (end2 - start2))

获得的素数总和：142913828922
检查每个数的素数所用时间为 0.647822 秒

start3 = time.time()
sum_3 = find_sum_of_primes_upto_num_with_sieve(build_sieve_eratosthenes_linear, test_num)
end3 = time.time()
print("Sum of primes obtained: ", sum_3)
print("Time taken by checking primality of each number is %f sec" % (end3 - start3))

获得的素数总和：142913828922
检查每个数的素数所用时间为 1.561308 秒

标签： python-3.xalgorithmtime-complexityprimessieve-of-eratosthenes

解决方案

我在每个例程中都放了一个简单的迭代计数器，并从 10^3 到 10^7 运行 10 的幂

build_sieve_eratosthenes：

    1000 has     1958 iterations in sieve
   10000 has    23071 iterations in sieve
  100000 has   256808 iterations in sieve
 1000000 has  2775210 iterations in sieve
10000000 has 29465738 iterations in sieve

build_sieve_eratosthenes_linear：

    1000 has      831 iterations in sieve_linear
   10000 has     8770 iterations in sieve_linear
  100000 has    90407 iterations in sieve_linear
 1000000 has   921501 iterations in sieve_linear
10000000 has  9335420 iterations in sieve_linear

您的linear函数不是线性的：注意内部循环，它运行pos时间......并且pos是找到的素数数量的计数，它不是一个常数。

linear比“正常”函数增长得更慢，并且总体上的迭代次数要少得多。但是，每次迭代的成本更高，这就是您看到“倒置”时间的原因。在您的功能中，找到的每个数字和每个“划掉”都更昂贵linear；较慢的增长没有赶上你的限制，只有 2*10^6，而不是我的限制 10*7。如果这对您来说值得的话，您可以将其推断出大约一天，以便更好地了解适当的时机……但核心“问题”是每个数字的处理速度较慢。

对于细节好奇，这里是完整的输出：

1000 has 1958 iterations in sieve
Sum of primes obtained:  76127
Time taken by checking primality of each number is 0.000904 sec
10000 has 23071 iterations in sieve
Sum of primes obtained:  5736396
Time taken by checking primality of each number is 0.008270 sec
100000 has 256808 iterations in sieve
Sum of primes obtained:  454396537
Time taken by checking primality of each number is 0.067962 sec
1000000 has 2775210 iterations in sieve
Sum of primes obtained:  37550402023
Time taken by checking primality of each number is 0.428727 sec
10000000 has 29465738 iterations in sieve
Sum of primes obtained:  3203324994356
Time taken by checking primality of each number is 5.761439 sec
1000 has 831 iterations in sieve_linear
Sum of primes obtained:  76127
Time taken by checking primality of each number is 0.001069 sec
10000 has 8770 iterations in sieve_linear
Sum of primes obtained:  5736396
Time taken by checking primality of each number is 0.010398 sec
100000 has 90407 iterations in sieve_linear
Sum of primes obtained:  454396537
Time taken by checking primality of each number is 0.107276 sec
1000000 has 921501 iterations in sieve_linear
Sum of primes obtained:  37550402023
Time taken by checking primality of each number is 1.087080 sec
10000000 has 9335420 iterations in sieve_linear
Sum of primes obtained:  3203324994356
Time taken by checking primality of each number is 11.008726 sec

推荐阅读