素数是大于1其因子为1和他本身的自然数,大于1非质数的自然数称为合数。例如,5是素数,它的约数只有1和5;6是合数,它的因子除了1和6外,还有2和3。任何大于1的整数均可被表示成一串唯一素数之乘积。
欧几里德(Euclid)在公元前300年证明了质数的无限性(欧几里得定理)。测试素数包含试除法,即逐一测试 √n 之间的整数。试除法是非常慢的,效率比较高的有 Miller–Rabin素数测试, AKS素数测试。
许多有关素数的问题依然未解,如著名的哥德巴赫猜想(每个大于2的偶数可表示成两个素数之和)及孪生素数猜想(存在无穷多对相差2的素数)。素数被用于加密中,如RSA(公钥加密)利用了难以将大数分解成两素数之积的性质。
现在给你一个2到2*109的素数p,请你跟他打个招呼吧。