C语言中求素数的两种方法.c

简介：
本程序展示了在C语言中寻找素数的两种经典算法：试除法和快速筛选法（埃拉托斯特henes筛法），适用于编程学习与实践。 素数又称质数，指的是除了1和它本身以外不能被任何整数整除的数字。例如，17是一个素数，因为它无法被2到16之间的任意一个整数整除。 判断一个整数m是否是素数的方法有两种： - 第一种方法是从2开始直到m-1之间每一个整数去除m，如果都不能将其整除，则可以确定m为素数。 - 第二种更为简化的方式则是只需检查2到√m之间的每个数字能否将m整除。例如，判断17是否是素数时，仅需用它被2至4的各数字进行测试即可；由于它们均无法整除17，则可以得出结论：17是一个素数。 原因在于如果一个大于一的正整数m能够被2到m-1之间的某个整数d（d不等于m）整除，那么必存在另一个因子n使得mn=m。此时，该对因子中至少有一个小于或等于√m，而另一个则必然大于或等于√m。例如，在考虑数字16时，尽管它能被2、4和8所整除，但这些因数的组合可以简化为：16=2*8（一个因子小于或者等于√16即4），以及16=4*4（恰好是它的平方根）。因此，仅需验证m在2到√m之间的数字是否能将其整除即可。