n 과 같은 소수 개 수 를 구하 다.

1888 단어
에 씨 체 법 (Eratosthenes 선별 법) 알고리즘 기본 사상: 자연수 n 이내 의 모든 소 수 를 얻 으 려 면 n1 / 2 보다 크 지 않 은 모든 소수 의 배 수 를 제거 해 야 하고 나머지 는 소수 이다.체 수치 범위 n 을 제시 하고 n 이내 의 소 수 를 찾 아 라.먼저 2 로 체 로 쳐 서 2 를 남기 고 2 의 배 수 를 제거한다.2 의 다음 체 에 걸 리 지 않 은 숫자, 즉 3 체 로 3 을 남 겨 두 고 3 의 배 수 를 제거한다.이어서 다음 질 수 5 체 로 5 를 남기 고 5 의 배 수 를 제거한다.끊임없이 반복 하 다.
bool a[1000003];//  i     
int main()
{
    int n;
    while(cin>>n)
    {
        memset(a, 0, (sizeof(bool))*1000003);

        for(int i=2;i<=sqrt(n);i++)//     
        {
            if(a[i]==1) continue;
            for(int j=2;j*i<=n;j++)
            {
                    a[j*i]=1;
            }
        }
        int ans=0;
        for(int i=2;i<=n;i++)
        {
            if(a[i]!=1)
                ans++;
        }
        cout<

좋은 웹페이지 즐겨찾기