• { • int i,n,t=0; • for(n=1;n<=100;n++) • { • for(i=2;i<=n;i++) • { • if(n%i==0) • break; • } • if(n==i) • { • printf("%-8d", n);//数据占8个宽度，并左对齐； • t++; •
如何判断一个数是素数？
C/C++
基本思想
判断一个整数m是否为素数，只需用2~m-1之 间的每一个整数去除，如果都不能被整除，那 么m就是一个素数。 其实可以简化，m不必被2~m-1之间的每一个 整数去除，只需被2~ m 之间的每个数去除就 可以了。例如判别17是否为素数，只需使2~4 之间的每一个整数去除。为什么可以做如此简 化呢？因为如果m能被2~m-1之间任意整数整 除，如果这个数大于 m ，那这个数必定对应 的还有一个比 m 小的因子（以16为例，2、8是 它的因子，8大于4，2小于4）。
• • • • • • • • • • • • • • • •
else
{
printf("FALSE\n"); } return 0; } char isPrime(int n) { int i; char c=TRUE; if(n==2){ c=TRUE;} else if(n>2) { if(n%2==0) {c=FALSE;}
• if (t%5==0) //每输出5个素数后换行； • printf ("\n"); //字符输出函数； • } • } • printf("\n"); • • printf("1-100内共有以上%d个质数（素数）。\n", t);
• return 0; • }
方法三：
• void main(){ • int i,k,m; • scanf("%d",&i); • k=sqrt(i); //判别i是否为素数，只需使2~根号i之间的每 一个整数去除 • for(m=2;m<=k;m++) • if(i%m==0)break; • if(m>k) • printf("%d是素数 ",i); • else printf("%d不是素数",i); • }
源程序
• • • • • • • • • • • • • #include<stdio.h> #include<math.h> #define TRUE 1 #define FALSE 0 int main() { int n; char isPrime(int n); //声明函数isPrime printf("Please enter a number:"); scanf("%d\n",&n); if(isPrime(n)==TRUE){ printf("TRUE\n"); }
运行结果
• • • • • • • • • • • • • • • • • • else
{
for(i=3;i<=sqrt(n);i+=2) { if(n%i==0) { c=FALSE; break; } } } } else { c=FALSE; } return c; }
方法二：
• • • • • • • • • • • • • • • • bool isprime(int a) { for(int i=2;i<=sqrt(a);i++) if(a%i==0) return false; return true; } void main(){ int a; printf("请输入："); scanf("%d",&a); if(isprime(a)) printf("是素数\n"); else printf("不是素数\n"); }