#1456 거의 소수

이번 문제는 소수를 구하는 문제입니다.  난이도는 Silver I 정도로 평가됩니다.

 

소수를 구하는 방법은 여러가지가 있는데, 일단은 2부터 n까지 숫자중 소수를 구하는 것이라면 \(O(n \sqrt {n} )\) 정도의 알고리즘으로 구할 수 있습니다.  에라토스테네스의 체를 이용하면, 메모리 공간이 좀 들겠지만, 가장 준수한 효율로 소수를 구할 수 있습니다.

 

거의 소수는 소수 \(p\)에 대해서 \(p^N\) 형태로 표현되는 수를 말합니다.  소수 자체는 거의 소수가 아니므로 실제로 주어진 범위안에서 구할 소수는 \( \sqrt {n} \) 범위입니다.

 

주어진 범위가 a ~ b 까지이므로 2 ~ b 까지의 거의 소수 개수를 구한 후 2 ~ a-1 까지의 거의 소수 개수를 빼주면 됩니다.

숫자의 범위가 \(10^{14}\) 정도가 아니었다면 log 함수를 이용해서 푸는 것이 가장 좋습니다.  예를 들어서 1000이하의 2의 멱승의 수는 \( \lfloor \log_{2} {1000} - 1 \rfloor \)로 표현할 수 있으니까요.

 

제가 짠 소스를 첨부합니다.  소스는 참조용으로 봐주세요.

 

//----------------------------------------------------------
//    baekjoon #1456 - Nearly Prime Number
//        - by Aubrey Choi
//        - created at 2020-02-15
//----------------------------------------------------------
#include <stdio.h>
#include <math.h>

int powercount(long long s, long long e, long long p)
{
    int r = 0;
    for(long long pp=p;pp<=e/p;) r+=(pp*=p)>=s;
    return r;
}
int main()
{
    long long s, e, p, i, r = 0, q;
    static char sv[10000004];
    scanf("%lld%lld",&s,&e);
    q = sqrt(e)+0.5;
    r += powercount(s, e, 2);
    for(p=3;p<=q;p+=2)
    {
        if(sv[p]) continue;
        for(i=p*p;i<=q;i+=2*p) sv[i]=1;
        r += powercount(s, e, p);
    }
    printf("%lld\n", r);
}