글 읽기 - 반례를 알 수 있을까요?

tjdgnsqn3 6년 전 0

isPrimeNumber에 2 ~ 1^7 의 소수를 체크해주고,

primeNumber에 소수들을 차례대로 넣습니다.

primeNumber를 가지고 min ~ max에 소수의 n승이 있는지 판단하고 count를 ++해줍니다.

#include <cstdio>
/**
 * https://www.acmicpc.net/problem/1456
 * BOJ 백준온라인져지 1456 거의 소수 풀이
 */
int main(){
    long long min, max;
    int count = 0;
    scanf("%lld%lld", &min, &max);
    bool *isPrimeNumber = new bool[(int)1e+7 + 1];
    int *primeNumber = new int[(int)1e+7 + 1];
    int cnt = 0;
    for(long long i = 2; i * i <= max ; i++){
        if(!isPrimeNumber[i]){
            for(long long j = i * 2; j * j <= max; j += i) isPrimeNumber[j] = true;
            primeNumber[cnt++] = i;
        }
    }
    
    for(int i = 0; i < cnt; i++){
        long long n = primeNumber[i];
        while(primeNumber[i] >= min / n && primeNumber[i] <= max / n){
            count++, n *= primeNumber[i];
        } 
    }

    printf("%d", count);
}

tjdgnsqn3 6년 전 0

찾았습니다.

5 5

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

문제

문제

출처

ICPC

반례를 알 수 있을까요?

tjdgnsqn3 6년 전 0

tjdgnsqn3 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말