[5615] 아파트 임대

https://www.acmicpc.net/problem/5615

5615번: 아파트 임대

<문제>

매우 어려운 문제였다. 결론적으론 소수판별 문제인데...

이 문제에 사용된 소수판별을 논하기 전에 기본적인 소수판별에 대해서 먼저 정리해보자.

 

소수판별을 단순하게 구현하면 O(N)이다.

2부터, n-1까지 %연산을 하다 0이되는 순간이 1번이라도 있으면 소수가 아니다.

 

하지만, 모든 합성수는 sqrt(N) 이하의 인수를 갖는다는 사실을 적용해

같은 %연산에 브루트포스적인 방법이여도 시간복잡도를 O(sqrt(N))으로 최적화가 가능하다.

일반적으로 사용할법한 소수판별은 여기에 에라토스테네스의 체를 더하는 방법이다.

 

에라토스테네스의 체는 단일대상 판별이 아닌, '구간에 대한 소수의 리스트'를 뽑고싶을때 사용한다.

가령, 100만부터 1천만까지의 소수의 목록을 찾고싶으면, 에라토스테네스의 체가 900만번의 O(sqrt(N))보다 훨씬 빠르다. 

에라토스테네스의 체는 시간복잡도가 O(Nlog(log(N)))이 나온다.

복잡하니 O(NlogN)보다 살짝 빠르다고만 생각해도 되겠다. 

 

여기까지 정리해보자. 소수판별문제는 두개로 쪼갤 수 있다.

아래만 제대로 이해하고 있으면, 일반적으로는 충분하지 않을까 싶다.

1) 단일대상 소수판별  -> O(sqrt(N))

2) 구간대상 소수판별(에라토스테네스의 체)-> O(Nlog(logN)).... O(NlogN)보다도 빠르다!

 

이제 여기서 조금 더 심화시켜보자.

2)를 심화시키는 알고리즘은 아직 뾰족한건 없지만(기원전 알고리즘이 아직도 최선이다)

초반 몇개의 수에대해 하드코딩된 소수를 바탕으로 합성수를 먼저 거르고 시작하는 방법이있다.

궁금하다면 아래를 참조해보자.

https://stackoverflow.com/questions/17892313/sieve-of-eratosthenes-with-wheel-factorization

https://en.wikipedia.org/wiki/Wheel_factorization

Wheel factorization - Wikipedia

Sieve of Eratosthenes with Wheel Factorization

1)을 개선해서, 단일대상 소수판별을 더 빠르게할수는 없을까?

확률적이지만 빠르게할 수 있는 방법이 있다. 

이번에 사용한 알고리즘은 밀러라빈 소수판별법이다.

https://ko.wikipedia.org/wiki/%EB%B0%80%EB%9F%AC-%EB%9D%BC%EB%B9%88_%EC%86%8C%EC%88%98%ED%8C%90%EB%B3%84%EB%B2%95

밀러-라빈 소수판별법 - 위키백과, 우리 모두의 백과사전

 

이 문제에 적용하기 위해 필요한 부분을 보자.

-> 입력이 int범위라면 {2,7,61}에 대해 검사하면 충분하다.(long long같은 경우, 37까지의 소수면 충분하다)

 

또한, 리만가설이 참이라면 밀러라빈 소수판별법의 시간복잡도는

의 시간복잡도를 갖는다고 한다.

밀러라빈을 구현하는 방법의 차이인거 같은데, 같은 밀러라빈이여도 어떻게 구현하느냐에 따른 

퍼포먼스 차이가 존재하는것으로 보인다. FFT랑 페르마의 소정리에 익숙해지고 다시한번 봐야겠다.

참고 : https://casterian.net/archives/396

밀러-라빈 소수 판별법 (Miller-Rabin Primality Test) – The Casterian

<소스코드>

#include<stdio.h>
typedef unsigned long long ull;
int n;
ull pow(ull x, ull y, ull p) {
    ull res = 1;
    x %= p;
    while (y > 0) {
        if (y & 1) {
            res *= x;
            res %= p;
        }
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
bool miller_rabin(ull n, ull a) {
    int i;
    ull r = 0;
    ull d = n - 1;
    while (d % 2 == 0) {
        r++;
        d = d >> 1;
    }
    ull x = pow(a, d, n);
    if (x == 1 || x == n - 1) return true;
    for (i = 0; i < r - 1; i++) {
        x = pow(x, 2, n);
        if (x == n - 1) 
            return true;
    }
    return false;
}
bool isPrime(ull n) {
    int i;
    ull prime[5] = { 2,3,5,7,11 };
    if (n <= 1)return false;
    if (n == 2 || n == 3||n==5||n==7||n==11)return true;
    if (n % 2 == 0)return false;
    for (i = 0; i < 5; i++) {
        ull a = prime[i];
        if (miller_rabin(n, a) == false)
            return false;
    }
    return true;
}
int main(void) {
    int i,cnt=0;
    ull target;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%lld", &target);
        if (isPrime(2 * target + 1))cnt++;
    }
    printf("%d", cnt);
}