三年来我写过的那些判素数函数

判素数，是每个学编程的人都掌握的基本函数。而它，也见证了我从循环一步步学到动态规划，从加减乘除取余都无法熟练运用到STL以下熟练运用的过程。

一开始，我就只会在main函数里写程序。那时候的判素数，基本上相当于用void写的。

void pzs()
{
    int n,y=0;
    cin>>n;
    for(int i=2;i<=n;i++)
    {
        if(n%i==0)
        {
            y=1;
            break;
        }
    }
    if(y==0)    cout<<"YES";
    else    cout<<"NO";
    return;
}

后来我学会了将y改成bool，这样能节省空间(至少当时是那样想的）

void pzs()
{
    int n;bool y=0;
    cin>>n;
    for(int i=2;i<=n;i++)
    {
        if(n%i==0)
        {
            y=1;
            break;
        }
    }
    if(y==0)    cout<<"YES";
    else    cout<<"NO";
    return;
}

等我学到了函数(与循环一起学的)和string类，我学会了不用直接在判素数函数里cin,cout

string pzs(int n)
{
    bool y=0;
    for(int i=2;i<=n;i++)
    {
        if(n%i==0)
        {
            y=1;
            break;
        }
    }
    if(y==0)    return "YES";
    else    return "NO";
}

紧接着，我又把string改成了int

int pzs(int n)
{
    bool y=0;
    for(int i=2;i<=n;i++)
    {
        if(n%i==0)
        {
            y=1;
            break;
        }
    }
    return y;
}

很快，我学了bool函数，于是判素数函数又变成了这样：

bool pzs(int n)
{
    for(int i=2;i<=n;i++)
       if(n%i==0)    return false;
    return true;
    return;
}

这是一次“巨大”的"创新"。就在同一天，我学会了sqrt()函数，也将true,false改成了1,0。

bool pzs(int n)
{
    for(int i=2;i<=sqrt(n);i++)
        if(n%i==0)    return false;
    return false;
}

于是，我去OJ提交了程序。但这是错的。于是我给程序加了一行代码：

bool pzs(int n)
{
    if(i<2) return false;
    for(int i=2;i<=sqrt(n);i++)
        if(n%i==0)    return false;
    return false;
}

很长一段时间，我用的都是这段程序。直到我知道i*i比sqrt()运行的快：

bool pzs(int n)
{
    if(i<2) return false;
    for(int i=2;i*i<=n;i++)
        if(n%i==0)    return false;
    return false;
}

半年前，我学会了筛选找素数。于是我写了这样一段程序（那时候大家都在冲进度，所以一次就对了）：

bool s[1000001];
bool pzs(int n)
{
    memset(s,0,sizeof(s));s[1]=1;
    for(int i=2;i*i<=n;i++)
    {
        if(s[i]==0)
        {for(int j=i*i;j<=n;j+=i)    s[j]=1;}
    }
    return s[n];
}
            

就这样，我学会了判素数函数。判素数函数也伴我走过了这三年。