标签: primality-test

为了测试一个数字是否为素数,为什么我们必须测试它是否只能被该数字的平方根整除？

我想问一下这是否是检查数字是否为素数的正确方法？因为我读到0和1不是素数.

int num1;

Console.WriteLine("Accept number:");
num1 = Convert.ToInt32(Console.ReadLine());
if (num1 == 0 || num1 == 1)
{
    Console.WriteLine(num1 + " is not prime number");
    Console.ReadLine();
}
else
{
    for (int a = 2; a <= num1 / 2; a++)
    {
        if (num1 % a == 0)
        {
            Console.WriteLine(num1 + " is not prime number");
            return;
        }

    }
    Console.WriteLine(num1 + " is a prime number");
    Console.ReadLine();
}

作为我自己的练习,我正在实施Miller-Rabin测试.(通过SICP工作).我理解费马的小定理并且能够成功地实现它.我在米勒 - 拉宾测试中被绊倒的部分是这个"1 mod n"业务.是不是1 mod n(n是一些随机整数)总是1？所以我很困惑"1模数n的非平方根"可能是什么,因为在我看来"1 mod n"在处理整数值时总是1.我错过了什么？

所以我设计了以下函数来查看给定数字是否是Haskell中的素数(它假设第一个素数是2):

isPrime k = length [ x | x <- [2..k], k `mod` x == 0] == 1

它有继续评估的明显缺陷,即使它可被几个数字整除:(.当使用列表推导找到多个解决方案时,是否有任何理智的"削减"评估的方法？

另外,你会尝试哪些其他实现？我不是在这里寻找表现,我只是想看看是否还有其他更"冒险"的方式来做同样的事情.

我现在正在阅读Doets和Van Eijck撰写的"The Haskell Road to Logic,Math,and Programming"一书.在本书之前,我从未接触过任何函数式编程语言,因此请记住这一点.

在本书的早期,它还提供了以下用于素性测试的代码:

ldp :: Integer -> Integer
ldp n = ldpf primes1 n

ldpf :: [Integer] -> Integer -> Integer
ldpf (p:ps) n | rem n p == 0 = p 
              | p^2 > n      = n
              | otherwise    = ldpf ps n

primes1 :: [Integer]
primes1 = 2 : filter prime [3..]

prime :: Integer -> Bool
prime n | n < 1     = error "not a positive integer"
        | n == 1 …

给定n,求m使得m是小于n的最小半素.

下一个素数非常简单,半素质不那么简单.需要说明的是,只需要半刚性,尽管同时获取因子会很方便.

我想到了一些方法,但我确信有更好的方法.

算术运算假定为O(1).我使用了Eratosthenes的Sieve,它是O(n log log n),我知道Atkin的Sieve,但我喜欢我的半优化的Eratosthenes.

从n算起

从n开始计数,当你找到半数时停止.

这看起来真的很愚蠢但如果有一个O(log n)半素测试或O(1)测试给出下面的素数,这可能比其他2更快.

Semiprime分布似乎远高于主要分布,因此通过良好的半素测试,这实际上可能优于O(n).

2.倒计时

定义prev(x)和next(x)并分别给出上一个和下一个素数,如果素数存储在树中或使用列表二进制搜索,则可以是O(log n).

先做筛子.

从p = prev(sqrt(n))开始,q = next(n/p).当pq <= n时,转到下一个q.如果pq小于目前为止的最小值,则将其记录为新的最小值.继续前一个p,直到用完p进行测试.

这可以保证找到正确答案,但速度相当慢.仍然是O(n log n),所以也许可以接受.

3.计票数量增加

像往常一样从筛子开始.为O(1)素性测试创建筛子的哈希集视图.

从p = 2开始.通过素数迭代到sqrt(n).对于每个p,得到q =(((n/p + 1)/ 2)*2)+1 =(((n/p + 1)>> 1)<< 1)| 1.虽然到目前为止pq小于最小值且q不是素数,但是将q加2.如果pq仍小于最小值,则将其记录为新的最小值.

我在Java中实现了#1和#3,两者都使用了相同的Eratosthenes Sieve实现.大部分的运行时间都花在筛选上,所以如果要进行优化,那就是在筛子中.在一些优化之后,向上计数(#1)击败计数(#3),在最后一次和最大测试(11位十进制数n)中快两倍.

但仍然有希望,因为需要延长筛子的距离取决于最大数量的主要测试.如果存在具有较低质数测试界限的半素测试,则计数方法可能更快.

当然有一个更好的算法？或者至少有更好的方法来实现这个？

我正在寻找一种算法来进行素数测试(如10 ²⁰⁰)数字.有没有好的算法？

理想情况下,我更喜欢一种非概率算法.

注意:数字超过50且少于200位.

我试图根据FIPS 186-3 C.3.1中的描述实施Miller-Rabin素性测试.无论我做什么,我都无法让它发挥作用.说明是非常具体的,我不认为我错过任何东西,但我得到true非素数值.

我做错了什么？

template <typename R, typename S, typename T>
T POW(R base, S exponent, const T mod){
    T result = 1;
    while (exponent){
        if (exponent & 1)
            result = (result * base) % mod;
        exponent >>= 1;
        base = (base * base) % mod;
    }
    return result;
}



// used uint64_t to prevent overflow, but only testing with small numbers for now
bool MillerRabin_FIPS186(uint64_t w, unsigned int iterations = 50){
    srand(time(0));
    unsigned int a = …

我写了isPrime函数.它检查给定的数字是否为素数.最后的"主要"列表是单独给出的.

prime :: [Integer]
prime = 2 : filter isPrime [3..]
isPrime :: Integer -> Bool
isPrime n | n < 2 = False
isPrime n = all (\p -> n `mod` p /= 0) . takeWhile ((<=n) . (^2)) $ prime

我认为如果可能的话,将两个函数合并为一个总是更好.所以我将isPrime和prime合并到一个函数isPrime2中.但isPrime2的表现非常糟糕.

isPrime2 :: Integer -> Bool
isPrime2 n | n < 2 = False
isPrime2 n = all (\p -> n `mod` p /= 0) . takeWhile ((<=n) . (^2)) $ 2 : filter isPrime2 [3..]

isPrime 40000000000000000001 …

我正在阅读关于主要测试算法的文章并找到了AKS素性测试.这个算法可以在Scheme或C++中实现吗？

有没有人尝试过实施AKS测试？