质数测试

简介 我尝试利用C语言的速度和高效的算法来进行质数测试。背景 你需要了解两个事实。1. 如果一个数可以分解成两个数的乘积，那么至少其中一个数应该小于或等于它的平方根。2. 每个质数都可以表示为 6k+1 或 6k-1 的形式。解释 我刚才提到的这两个事实在这里被转换成代码。

#include <stdio.h>

#include <math.h>


main()
{
unsigned long int testno;
unsigned long int i=0;
unsigned long int testsqrt;
printf("Enter number for checking : \n");
scanf("%lu",&testno);
if(testno==2||testno==3){
printf("\nPrime");
getch();
exit();}
if(((testno+1)%6==0)||(((testno-1)%6)==0)||(testno%2!=0)||(testno%3!=0))
{
testsqrt=ceil(sqrt(testno));
for(i=5;i<=testsqrt;i++)
{
 if(i%2==0||i%3==0)
 continue;
 if(testno%i==0)
 {
 printf("\nNot Prime");
 getch();
 exit();
 }
}
}
else
{
printf("\nNot Prime");
getch();
exit();
}
printf("\nPrime");
getch();

} 

首先，它检查该数字是否为2或3，如果是其中之一，则打印该数字是质数。这一行

if(((testno+1)%6==0)||(((testno-1)%6)==0)||(testno%2!=0)||(testno%3!=0)) 

过滤掉大多数非质数。首先，它测试该数字是否可以表示为 6k+1 或 6k-1 的形式，然后测试它是否是2或3的倍数。如果它可以表示为这两种形式之一（6k+1 或 6k-1），那么它将继续进行检查循环。如果条件失败，程序在打印“不是质数”后退出。然后，testsqrt 存储 testno（用户输入的数字）的平方根。循环计数器 i 从 5 开始（2 和 3 已经过检查。每个 4 的倍数都可以被 2 整除，而 2 已经过检查）。然后，检查计数器是否为偶数或 3 的倍数。如果是，则程序继续下一次迭代。然后，程序检查 testno 是否是当前数字（计数器）的倍数。如果是，则程序打印“不是质数”。如果没有任何数字可以整除 testno，那么程序最终打印该数字是质数并退出。