求 1-N 的所有素數 （c++實作）

要求：求 1-N 所有的素數

素數定義：在大于1的自然數中，除了1和它本身以外不再有其他因數

思路：對于 1-N 中的某個數 k，判斷 k 在 2- （k-1）中是否有數 j 滿足 k%j==0，若有，則 k 不為素數；若沒有則 k 為素數。

代碼：

#include <iostream>

#include <vector>

using namespace std;

int main()

{

    int n;

    cin>>n;

    int num=0,k;

    vector<int> s;

    for(int i=2;i<=n;i++)

    {

        int flag=1;

        for(int j=2;j<=i-1;j++)

        {   

            k=i%j;

            if(k==0)

            {

                flag=0;

                break;

            }

        }

        if(flag==1)

        {

            s.push_back(i);

        }

    }

    num=s.size();

    int total=0,sc=0,en=num-1;

    while(sc<=en)

    {

        if((s[sc]+s[en])==n)

        {

            sc++;

            en--;

            total++;

         }

        else if((s[sc]+s[en])<n)

        {

            sc++;

        }

        else if((s[sc]+s[en])>n)

        {

            en--;

        }

    }

    cout<<total<<endl;

    return 0;

}