下面是求素数的代码（教材上的） 看不懂 请高手指点 谢谢了
#include<stdio.h>
int main(void)
{
int i,no;
int prime[500];
int ptr = 0;
unsigned long counter = 0;
prime[ptr++] = 2;
prime[ptr++] = 3;
for (no=5; no<=1000; no+=2){
int flag = 0;
for(i=1; counter++, prime[i] * prime[i]<=no; i++){
counter++;
if(no%prime[i]==0){
flag = 1;
break;
}
}
if(!flag)
prime[ptr++] = no;
}
for(i=0; i<ptr; i++)
printf("%d\n",prime[i]);
printf("除的次数:%lu\n",counter);
return(0);
}
[解决办法]
挺精妙的算法，判断一个数是否为素数，比如n，只要判断能否整除2，3,4,5,6....到n的开方即可，当然判断2，3.。。到n也行，不过后面的比较少是没必要的。这个程序只要判断2，3，5，7.。到n的开方即可，算法效率更高
- C/C++ code
#include <stdio.h> int main(void) { int i,no; int prime[500]; int ptr = 0; unsigned long counter = 0; prime[ptr++] = 2; //prime[0]=2 prime[ptr++] = 3; //prime[1]=3 for (no=5; no <=1000; no+=2){ //no为要判断的数 int flag = 0; //flag为0是素数 for(i=1; counter++, prime[i] * prime[i] <=no; i++){ //比较条件为prime[i] * prime[i] <=no counter++; if(no%prime[i]==0){ //判断条件为no能否整除prime[i] flag = 1; break; } } if(!flag) //flag为0,赋值 prime[ptr++] = no; } for(i=0; i <ptr; i++) printf("%d\n",prime[i]); printf("乘除的次数:%lu\n",counter); getchar(); return(0); }
[解决办法]
- C/C++ code
#include<stdio.h>int Q(int z);int Q(int z){int rtn = 0;int i,j; for(i= 1;i <= z;i++) { for(j=1 ;j<=z;j++) { if((i!=1) && (j!=1)) { if(i*j==z ) { rtn=1; } } } }return rtn;}int main(){int n;int i; for(i=2;i<=100;i++) { n=Q(i); if (n==1) { continue; } else if (n==0) { printf("%d\t",i); } }printf("\n");system("pause");return 0;}
[解决办法]
最笨的方法：
素数就是仅能衩1和它自身整除的整数。判定一个整数n是否为素数就是要判定整数n能否被除1和它自身之外的任意整数整除，若都不能整除，则n为素数。
程序设计时i可以从2开始，到该整数n的1/2为止，用i依次去除需要判定的整数，只要存在可以整除该数的情况，即可确定要判断的整数不是素数，否则是素数
- C/C++ code
#include<stdio.h>int main(){ int n1,nm,i,j,flag,count=0; do{ printf("Input START and END=?"); scanf("%d%d",&n1,&nm); /*输入求素数的范围*/ }while(!(n1>0&&n1<nm)); /*输入正确的范围*/ printf("...........PRIME TABLE(%d--%d)............\n",n1,nm); if(n1==1||n1==2) /*处理素数2*/ { printf("%4d",2); n1=3;count++; } for(i=n1;i<=nm;i++) /*判定指定范围内的整数是否为素数*/ { if(!(i%2))continue; for(flag=1,j=3;flag&&j<i/2;j+=2) /*判定能否被从3到整数的一半中的某一数所整除*/ if(!(i%j))flag=0; /*若能整除则不是素数*/ if(flag) printf(++count%15?"%4d":"%4d\n",i); } return 0;}
[解决办法]