用筛法求之N内的素数。 -题解(C++代码)筛法和一般法

筛法

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=1;i<n+1;i++)//把全部数都输入到数组中 
    {
        a[i]=i;
    }
    for(int j=2;j<=n;j++)//从2开始，因为素数最小是2，循环n以内的所有的数 
    {
        if(a[j]!=0)//判断这个数是不是一个素数的整数倍 
        {
            for(int k=2;j*k<=n;k++)
            {
            a[j*k]=0;//判断这个数是不是一个素数的整数倍，如果是，变成0 
            }
            cout<<a[j]<<endl;
        }//即2是素数，然后把2的倍数标为0，因为他们不是素数，继续向后循环，找到每一个素数； 
    }
    return 0;
}

一般法

#include<iostream>
using namespace std;
bool isprime(int i)
{
    bool boll=false;
    for(int j=2;j*j<=i;j++)
    {
        if(i%j==0)
        {
            return boll;
            break;
        }
    }
    boll=true;
    return boll;
}
int main()
{
    int n;
    cin>>n;
    bool ball=false;
    for(int i=2;i<=n;i++)
    {
        if(isprime(i))
        cout<<i<<endl;
    }
    return 0;
}