C 在区间 k^3 到 (k + 1)^3 中找到素数的有效方法

Question

在讲座中，我们被告知对于所有 k > 1，在 k³ 和 (k + 1)³ 之间至少存在一个素数。我现在想知道如何找到这样一个素数 在 C 中高效地。我知道埃拉托色尼筛法，但我不知道如何在不污染内存的情况下实现它。感谢您的帮助。

Answer 1

你需要污染你的记忆以提高寻找质数的速度。有一种简单的方法，实施起来既快速又简单。

primes = list of prime number below sqrt( (k+1)^3 )
for i = k^3 + 1 to (k+1)^3 :
     is_prime = true
     for p in primes:
           if (i % p == 0) :
              is_prime = false
              break
     if (is_prime):
          print(i)

要生成低于 sqrt ( (k+1)^3 ) 的素数列表，您可以使用埃拉托色尼筛法。使用这种方法，您最多只需要使用 (k+1)^1.5 内存。

Answer 2

答案在很大程度上取决于 k 的大小。如果 k 很小，小于 10**3 左右，Eratosthenes 筛法就可以很好地工作。但是如果 k 更大，更好的方法是使用 Miller-Rabin pseudoprimality test:

function isPrime(n, k=5)
    if n < 2 then return False
    for p in [2,3,5,7,11,13,17,19,23,29]
        if n % p == 0 then return n == p
    s, d = 0, n-1
    while d % 2 == 0
        s, d = s+1, d/2
    for i from 0 to k
        x = powerMod(randint(2, n-1), d, n)
        if x == 1 or x == n-1 then next i
        for r from 1 to s
            x = (x * x) % n
            if x == 1 then return False
            if x == n-1 then next i
        return False
    return True

有了它，您可以测试从 k 开始的每个奇数的立方。找一个质数应该不会花很长时间。

C 在区间 k^3 到 (k + 1)^3 中找到素数的有效方法

C Efficient way to find prime number in interval k^3 to (k + 1)^3

c

algorithm

primes