C语言求素数，以及优化

最开始因为计数的k，处理不当，始终得不到想要的数据，后来k的位置处理好了，中间的for循环是这样的

for(j=2;j<=i/2;j++) { if(i%j==0){ k++; break; } }效率不够；

后来在网上找了一下，发现大家都开平方

因为：如果a*b=n的话，那么最大情况就是a=b了，所以要对n开平方

第一种，普通的用开平方来计算

```

#include "stdio.h" #include "math.h" /* 求n以内的素数 */ int main(){ int i,j,n,k,p=0; scanf("%d", &n); for (i=2;i<=n;i++){ k=0; for(j=2;j<=sqrt(i);j++) { if(i%j==0){ k++; break; } } if (k==0) { printf("%d,",i); p++; continue; } } printf("\n",p); printf("p=%d\n",p); }

```

第二种方法，排除法，尚未优化

```

#include "stdio.h" #include "math.h" /* 求n以内的素数 */ int main(){ printf(" 请输入1--10000的数字：\n"); int n, i, j; int a[10001]; scanf("%d",&n); for (i=0; i<n; i++) { a[i] = 1; } printf(" %d 包含的素数有： ", n); for (i=2; i<=n; i++) { if (a[i]==1) { printf("%d ",i); for (j=2*i; j<=n; j=j+i) a[j] = 0; } } return 0; }

```

第二种方法