글 읽기 - c++, 채점하면 바로 틀렸습니다가 뜹니다..

kjw0914 3년 전 0

에라토스테네스의 체를 이용하여 소수를 먼저 구한다음(check_prime())

main함수의 for문에서 i=2부터 시작해서 i<=(n-i)까자 돌면서 i와 n-i 모두 소수면 cnt를 증가시키도록 했습니다

(is_prime[i]==true이면 i는 소수)

#include <iostream>
#include <stack>
#include <queue>
using namespace std;

const int MAX=1000000;
bool is_prime[MAX+1];

void check_prime(){
    fill_n(is_prime,MAX+1,true);
    is_prime[0]=false; is_prime[1]=false;

    for(int i=2;i*i<=MAX;i++){
        if(is_prime[i]){
            for(int j=i*2;j*j<=MAX;j+=i) is_prime[j]=false;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    check_prime();
    int t,n,cnt;
    cin >> t;
    while(t--){
        cnt=0;
        cin >> n;
        for(int i=2;i<=(n-i);i++){
            if(is_prime[i] && is_prime[n-i]) cnt++;
        }
        cout << cnt << '\n';
    }    
}

dldyddlwl 3년 전 1

for(int i=2;i*i<=MAX;i++)

{

if(is_prime[i])

{

for(int j=i*2;j*j<=MAX;j+=i) is_prime[j]=false;

}

이 부분에서 j의 제곱이 MAX가 아니라 j가 MAX 이하여야 합니다.

만약에 j의 제곱이 MAX이하여야 한다고 가정해봅시다. 그러면, 에라토스테네스의 체에 의해서

2의 배수가 지워져 갈겁니다. 2 4 6 8 10 12 ... 1000이 나오는 순간 1000^2 <= MAX 이고, 그 이후가 지워지지 않습니다.

따라서, 이 점만 유의해주세요!

kjw0914 3년 전 0

아 그렇네요!! 감사합니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c++, 채점하면 바로 틀렸습니다가 뜹니다..

kjw0914 3년 전 0

dldyddlwl 3년 전 1

kjw0914 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말