关于素数的算法（筛法求小于n的素数）

遇到了一个要求用筛法求小于n的素数的算法题目
以前在上课时也写过不少次求素数的算法，今天汇总一下，然后试一下筛法。

先写一个函数，功能是判断x是否是素数

int panduan(int x)  //判断x是否为素数
{
    if(x==1)return 0;       //1不是素数
    int i;
    int y=sqrt(x);			//x的“因数对”除了两个根号x相等外，其他的一对因数一定是一大一小
    for(i=2;i<=y;i++)
    {
        if(x%i==0)break;

    }
    if(i==y+1)return 1;   //素数返回1
    else return 0;
}

如果题目的要求是：
输入整数X
输出小于等于x的素数
那么只要在用一个循环，从1开始到x，依次判断是否为素数，并将素数输出就可以了：

int main()
{
    int x;
    cin>>x;
    for(int i=1;i<=x;i++)
    {
        if(panduan(i))cout<<i<<endl;
    }
    return 0;
}

这样就输出了小于x的素数：

所谓的筛法

筛法的处理过程：
1、假设输入x为30

2、初始的结果：
1,2,3,4,5,6,7,8,9,10
11,12,13,14,15,16,17,18,19,20
21,22,23,24,25,26,27,28,29,30

3、从1开始判断：
1是否是素数，不是素数，丢掉
结果变为：
2,3,4,5,6,7,8,9,10
11,12,13,14,15,16,17,18,19,20
21,22,23,24,25,26,27,28,29,30

2是否是素数，2是素数，去掉（2的倍数）&&（小于x的数）
结果为：
2,3,5,7,9
11,13,15,17,19
21,23,25,27,29

3是否是素数，3是素数，去掉（3的倍数）&&（小于x的数）
2,3,5,7
11,13,17,19
23,25,29

4已经去掉了，判断5，5是素数，去掉去掉（5的倍数）&&（小于x的数）
2,3,5,7
11,13,17,19
23,29

以上就是筛法的处理步骤。
代码：

#include <iostream>
#include <cmath>
using namespace std;
int panduan(int x)  //判断x是否为素数
{
    if(x==1)return 0;       //1不是素数
    int i;
    int y=sqrt(x);
    for(i=2;i<=y;i++)
    {
        if(x%i==0)break;

    }
    if(i==y+1)return 1;   //素数返回1
    else return 0;
}

int main()
{
    int A[10000]={0};
    int x;
    cin>>x;
    for(int i=1;i<=x;i++)
    {
        A[i]=i;
    }
    for(int i=1;i<=x;i++)   //从1筛到x
    {
        if(A[i]==0) ;   //循环到已经筛掉的数，不做任何处理
        else{           //循环到未处理过的数，进行判断
            if(!panduan(i))A[i]=0;      //不是素数，直接筛掉
            else{
                for(int j=i;j<=x;)      //将素数的倍数去掉
                {
                    int m=j/i;
                    m++;
                    j=m*i;
                    if(j<=x)A[j]=0;
                }
            }
        }
    }
    for(int i=1;i<=x;i++)
    {
        if(A[i]!=0)cout<<A[i]<<endl;
    }
    return 0;
}