前言：
今天敲了个埃式筛的求素数的程序，求1000以内素数的个数，犯了低级的数组越界的错误，在这里做个小记录，非常有意思；
给出代码：
#include<bits/stdc++.h> using namespace std; const int N = 1e4; int prime[N]; int cnt,cnts; void Isprime() { prime[0]=1; prime[1]=1; for(int i=2;i<=N;i++) { if(prime[i]==0) { for(int j=i*2;j<=N;j+=i) { prime[j]=1; } } } for(int i=1;i<=N;i++) { if(prime[i]==0) { prime[++cnt]=i; } } } int main() { Isprime(); for(int i=1;i<=1000;i++) { if(prime[i]<1000) cnts++; } cout<<cnts; }
很经典的一个埃式筛求素数的程序(用了同一个数组做了内存优化)，求前一千个数中素数的个数，答案应该是 168个，但是我的程序错误的求出了169个，于是我寻根溯源，不断地进行测试，发现cnt的初始值在函数中埃式筛的核心代码段被改变了，cnt是从 1开始的，而非0；
测试代码：
void Isprime() { prime[0]=1; prime[1]=1; cout<<cnt<<endl; for(int i=2;i<=N;i++) { if(prime[i]==0) { for(int j=i*2;j<=N;j+=i) { prime[j]=1; } } } cout<<cnt<<endl; for(int i=1;i<=N;i++) { if(prime[i]==0) { prime[++cnt]=i; } } }
测试输出：
0 1 169
当时我真是觉得离了天下之大谱了，我没有在埃式筛中改变计数器的值，但它自己好像有什么灵性一样自己改变了，我又看了好久并询问了学长学姐，终于找到了原因，罪魁祸首就是数组越界；
素数数组的大小是 N 下标就是 0 ~ N -1 但是我错误的让埃式筛的代码跑到了 N 的 位置，恰好定义的时候先定义的素数数组后定义的cnt计数器，导致 通过prime[N]错误的访问到了cnt的地址 这时恰好 N=1e4不是一个素数，被赋值成 1 ,计数器下标从 1 开始，我使用的又是++cnt计数器从二开始计数，所以多出的一个就找到了；
验证1：
为了证明我们的思想，我们可以输出prime[N-1]的地址和cnt的地址进行验证看他们是否相邻，int类型只要相差四个字节就是相邻
printf("%d\n",&prime[N-1]); printf("%d\n",&cnt);
果然他们是相邻的
验证2：
我们前面说 通过prime[N]错误的访问到了cnt的地址 ，我们也可以验证一下这个，给所有不是素数的值赋值一个1212，看cnt的初始值
for(int i=2;i<=N;i++) { if(prime[i]==0) { for(int j=i*2;j<=N;j+=i) { prime[j]=1212; } } } cout<<cnt<<endl;
结果：
结语：
当然我们也可以通过很多其他的方法进行验证，这个探索过程让我知道了数组千万不能越界，不然会带来很多乌龙，很多不可思议的错误，闹和我一样的笑话，数组千万不能越界！！！
最后给出正确的程序：(把埃式筛核心程序里的等于号都去掉即可)
**#include<bits/stdc++.h> using namespace std; const int N = 1e4; int prime[N]; int cnt,cnts; void Isprime() { prime[0]=1; prime[1]=1; for(int i=2;i<N;i++) { if(prime[i]==0) { for(int j=i*2;j<N;j+=i) { prime[j]=1; } } } for(int i=1;i<N;i++) { if(prime[i]==0) { prime[++cnt]=i; } } } int main() { Isprime(); for(int i=1;i<=1000;i++) { if(prime[i]<1000) cnts++; } cout<<cnts; }
以后敲代码要更加细心，加油！
