글 읽기 - 에라토스테네스의 체 질문입니다.

dlaqudanr 7년 전 0

처음엔 걍 노가다로 소수 구하기... 하다가 시간 초과가 안되서 질문글을 참고하니 에라토스테네스의 체를 이용하라고 하더군요

그래서 공부를 하고 이해 가는 소스로 제출 해보았으나

출력초과...

그리고 또 다른 소스로 하니 그건 되더라구요...

근데 그건 코드 이해가 잘 안갑니다.

설명해주실 수 있는분은 설명 부탁드립니다 ㅠㅜ 몇시간째 하는지 모르겠네요

// 여기는 제가 이해한 코드 입니다.
// 그러나 출력 초과로 실패하게 됩니다.

1.)

#include <iostream>
using namespace std;



int main()
{
   int a;
   int b;
   int *arr;
  
   cin >> a >> b;
 
   arr = new int[b];
   int c;
   
   //동적 배열에 담음
   for (c=a; c < b; c++)
   {
      arr[c] = c;
   
   }

   //에라토스테네스의 체
   for (int e = 2; e <= b; e++)
   {
      if (arr[e] == 0)
         continue;
      for (int c = e + e; c <= b; c += e)
      { //배수 처리
         arr[c] = 0;
      }
   }

   //출력
   for (int f = a; f <= b; f++)
   {
      if (arr[f]!=1 && arr[f] != 0)
         cout << arr[f] << endl;

   }

   return 0;
}







//////////// 여기는 성공하는 코드이나 이해가 안가는 코드입니다.

#include <cstdio>
#include <iostream>

int main(){
    bool isPrime[1000001];
    int a, b;
    scanf("%d%d", &a, &b);

    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i <= b; i++) {
        isPrime[i] = true;
    }

    // 이쪽 코드가 이해가 안갑니다.
    for(int i = 2; i * i <= b; i++){ 
        //여기서 왜 i*i<=b로  범위설정하는지 잘 모르겠습니다. for문의 몇번 돌리는지 범위설정
        int mult = 2;
        if (isPrime[i]) {
            for(int j = i * mult; j <= b; j = i * mult) {
                isPrime[j] = false; //이쪽도 설명가능시면 부탁드립니다. for문의 몇번 돌리는지 범위설정.
                mult++;
            }
        }
    }
// 여기까지 이해가 안갑니다.
    
    
    for(int i = a; i <= b; i++){
        if (isPrime[i]) {
            printf("%d\n", i);
        }
    }

    return 0;
}

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

문제

문제

출처

ICPC

에라토스테네스의 체 질문입니다.

dlaqudanr 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말