素数测试比较

Question

我在下面发现了一个新的素数测试，它确定 1000000007 是否为素数。

它的速度与其他现有素数算法相比如何？
它是否获得了最“无计算价值”的素性测试奖？

谢谢。

编辑

能够使用此处描述的此方法提高速度：

https://math.stackexchange.com/questions/3979118/speedup-primality-test

"所以从 x=n/2 到 n/2+√n/2 就足够了。有了这个改进，你的算法仍然会比你的 isPrimeNumber 例程慢一些- -只是因为计算 gcd 比计算整除率慢。这对于测试可能有 15-20 位数字的数字是可行的，但是你需要完全不同的方法来测试更大的数字，比如你提到的 183 位数字。” =12=]

// Primality Test
// Every n is prime if all lattice points on x+y=n are visible from the origin.

#include <stdio.h>
#include <stdint.h>
#include <math.h>


uint64_t gcd(uint64_t a, uint64_t b)
{
    return (b != 0) ? gcd(b, a % b) : a;
}


int isPrimeNumber(uint64_t n)
{
    if (n == 1) return 0;
    if (n == 2 || n == 3) return 1;
    if (n % 2 == 0) return 0;

    // Start near line x=y.
    uint64_t x = (n / 2) + 2;
    uint64_t y = n - x;
    uint64_t count = sqrt(n) / 2;

    for (uint64_t i = 0; i < count; ++i) {
        // Check lattice point visibility...
        if (gcd(x, y) != 1) return 0;
        x++; y--;
    }

    return 1;
}


int main(int argc, char* argv)
{
    uint64_t n = 1000000007;

    if (isPrimeNumber(n) == 1)
    {
        printf("%llu prime.", n);
    }
    else
    {
        printf("%llu not prime.", n);
    }

    return 0;
}

Answer 1

当您编写任何代码时，您应该进行基本调试以验证您的代码是否按照您的预期运行。运行你的代码就几个小号；打印 x 和 y 的值以验证它是否进行了正确的检查。

除此之外，如果混合使用整数和浮点变量，则应注意：隐式转换，例如从 float 到 unsigned 会导致数据丢失和完全错误的计算。编译器通常会对此发出警告；你应该在启用所有警告的情况下编译 -Wall 并注意编译器说的内容。

看起来您在计算过程中应该始终有 x + y = n - 这是您的不变量。这可以更容易地表达如下：

// initialization
x = n / 2;
y = n - x;
// it should be evident that your invariant holds here

do {
    ...
    x++; y--;
    // your invariant holds here too, by induction
}

素数测试比较

Primality Test Comparison

c

primes

primality-test