글 읽기 - 제곱 ㄴㄴ 수 시간초과 질문

kyk660 6년 전 0

소수만 뽑아내어서 에라토스테네스의 체를 이용하였는데 아무래도 잘못 이용한지 시간초과가 발생합니다 ㅠㅠ 이유가 무엇일까요. 도와드립니다ㅠㅠ

#include <iostream>
#include <cmath>
using namespace std;

bool isSquare[1000000];
bool prime[1000000];
long long Min, Max;

int main() {
    cin >> Min >> Max;
    long long new_max = 0, count =0;

    new_max = (long long) sqrt(Max);

    for(long long i = 0; i < 1000000; i++) {
        prime[i] = true;
        isSquare[i] = true;
    }

    for (long long i = 2; i <= new_max ; i++){
        if(prime[i]){
            for (long long j = i; j <= new_max; j++){
                if (j % i == 0 && i != j) {
                    prime[j] = false;
                }
            }//소수 판별 하는 부분
            long long start = (Min/(i*i) + 1)*(i*i);
            for(long long k = start; k <= Max; k++)
                if (k % (i*i) == 0) isSquare[k-Min] = false; //제곱수 ㄴㄴ 수 판별
        }
    }

    for(long long k = 0; k < Max-Min +1; k++) if(isSquare[k]) count++; // 전체 제곱수 판별

    cout << count;
}

symoon11 6년 전 1

소수가 1000보다 커지면 주어진 구간 내의 숫자 중에서 소수의 제곱으로 나누어떨어지는 숫자는 많아야 하나밖에 없을거에요. 그때는 for문을 안쓰시면 아마 되실겁니당

kyk660 6년 전 0

다른 풀이로 해결했습니다~ 감사합니다.

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

문제

문제

출처

ICPC

제곱 ㄴㄴ 수 시간초과 질문

kyk660 6년 전 0

symoon11 6년 전 1

kyk660 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말