1000000009是质数吗

Question

如题所述

Answer 1

1000000009是质数。
如果你想打哈希表/出题的话，可以用其作为模数。
我用以下C++代码测试过：
#include <bits/stdc++.h>
#define fo(i,a,b) for(i=a;i<=b;i++)
int i,n;
int main()
{
n=1e9+9;
fo(i,2,1e5) if(n%i==0) {printf("composite number"); return 0;}
printf("prime number");
}
程序输出"prime number"，表明1000000009在2~100000的范围内并无约数，故为质数。

Answer 2

质数（Prime number），又称素数，指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个正因数的数）。大于1的自然数若不是素数，则称之为合数。例如，5是个素数，因为其正约数只有1与5。而6则是个合数，因为除了1与6外，2与3也是其正约数。算术基本定理确立了素数于数论里的核心地位：任何大于1的整数均可被表示成一串唯一素数之乘积。为了确保该定理的唯一性，1被定义为不是素数，因为在因式分解中可以有任意多个1（如3、1×3、1×1×3等都是3的有效约数分解）。 古希腊数学家欧几里得于公元前300年前后证明有无限多个素数存在（欧几里得定理）。现时人们已发现多种验证素数的方法。其中试除法比较简单，但需时较长：设被测试的自然数为n，使用此方法者需逐一测试2与本回答被网友采纳