COJ 1030 소수 슬롯

http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1030
선형 체 소수 로 과연 훨씬 빠르다.

#include<cstdio>

#include<cstring>

#include<cstdlib>

#define MAXN 1300000

bool is_p[MAXN];



void calc()

{

    for( int i = 1; i < MAXN; i ++)

        is_p[i] = true;

    is_p[1] = false;

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

    {

        if( !is_p[i]) continue;

        for( int j = 2; i * j < MAXN; j ++)

            is_p[i * j] = false;

    }

}



int main()

{

    int n, k, cnt;

    calc();

    scanf( "%d", &n);

    while( n --)

    {

        scanf( "%d", &k);

        cnt = 0;

        for( int i = k; !is_p[i]; i ++)

            cnt ++;

        for( int i = k; !is_p[i]; i --)

            cnt ++;

        printf( "%d
", cnt);

    }

    return 0;

}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[BOJ] 2581번 소수

<< 문제 클릭! 입력 : 자연수 M, N (M, N은 10,000 이하의 자연수, M은 N보다 작거나 같다) 자연수 M이상 N 이하의 자연수 중 소수를 모두 찾는다. : 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

COJ 1030 소수 슬롯

좋은 웹페이지 즐겨찾기