Question

判断一个数是否为素数?

Answer 1

最直观的方法判断。

根据定义，因为素数除了1和本身之外没有其他约数，所以判断n是否为素数，根据定义直接判断从2到n-1的数中有没有N的约数？如果找不到这样的约数，那么这个数就是素数，否则就不是素数。

首先是看这个数是否是大于1的自然数，然后看它除了1和这个数字本身之外还有没有其他的因数，比如13，只有1和13两个因数，所以是素数，10有1和10，2和5四个因数，所以它不是素数。

含义

如果为合数，因为任何一个合数都可以分解为几个素数的积；而N和N+1的最大公约数是1，所以不可能被p1，p2，pn整除，所以该合数分解得到的素因数肯定不在假设的素数集合中。因此无论该数是素数还是合数，都意味着在假设的有限个素数之外还存在着其他素数。所以原先的假设不成立。也就是说，素数有无穷多个。