素数测试
August 8, 2018 · View on GitHub
质数（Prime number），又称素数，指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个正因数的数）。大于1的自然数若不是素数，则称之为合数。例如，5是个素数，因为其正约数只有1与5。而6则是个合数，因为除了1与6外，2与3也是其正约数.
一个 素性测试 是用于确定输入数是否为素数 的算法. 在数学的其他领域中,它用于密码学. 与整数分解不同,素性测试通常不会给出素数因子,只说明输入数是否为素数. 因子分解 被认为是计算上难以解决的问题,而素性测试相对容易 (其运行时间 是 输入大小 的多项式) .