백준 1124번: 언더프라임 (C++)

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

1124번: 언더프라임

---

Level: Silver I

Solved By: Miller Rabin, Pollard's Rho

 

소인수분해를 하는 알고리즘이라면 예전에 공부했었던 Pollard's Rho 알고리즘이 기억나서 코드를 가져와서 소인수 분해를 가능하게 했습니다. factors vector의 사이즈를 Miller Rabin에 물려서 소수로 판별이 난다면 res 값을 더해주는 식으로 답을 구했습니다.

#include <iostream>
#include <vector>
#define i128 __int128
#define ull unsigned long long
using namespace std;

vector<ull> factors;

ull power(i128 a, i128 b, i128 mod){ // 피연산자 또한 같은 자료형이어야 overflow가 안 남
    a %= mod;
    i128 ret = 1; // overflow 방지
    while(b > 0){
        if(b % 2 == 1) ret = (ret * a) % mod;
        a = (a * a) % mod;
        b /= 2;
    }
    return (ull)ret;
}

bool millerRabin(ull n, ull a){
    if(a % n == 0) return true;
    ull k = n - 1;
    while(true){
        ull temp = power(a, k, n);
        if(temp == n - 1) return true;
        if(k % 2) return (temp == 1 || temp == n - 1);
        k /= 2;
    }
    
}

bool isPrime(ull n){
    if(n == 1) return false;
    else if(n == 2) return true;
    else if(n % 2 == 0) return false;
    else{
        ull base[12] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
        for(auto a : base){
            if(n == a) return true;
            if(!millerRabin(n, a)) return false;
        }
        return true;
    }
}

i128 f(i128 x, i128 c, i128 mod){
    return ((x * x) % mod + c) % mod;
}

i128 gcd(i128 a, i128 b){
    while(true){
        i128 temp = a % b;
        a = b;
        b = temp;
        if(b == 0) return a;
    }
}

i128 abs128(i128 x){
    if(x < 0) return -x;
    else return x;
}

void factorize(i128 n){
    if(n == 1) return;
    else if(n % 2 == 0){
        factors.push_back(2);
        factorize(n / 2);
        return;
    }
    else if(isPrime(n)){
        factors.push_back(n);
        return;
    }
    else{
        i128 x, y, c, g = n;
        do{
            if(g == n){
                x = y = rand() % (n - 2) + 2;
                c = rand() % 10 + 1;
            }
            x = ((x * x) % n + c) % n;
            y = ((y * y) % n + c) % n;
            y = ((y * y) % n + c) % n;
            g = gcd(abs128(x - y), n);
        } while(g == 1);
        
        factorize(g);
        factorize(n / g);
    }
}

int main(){
    ull A, B; cin >> A >> B;
    int res = 0;
    for(ull i = A; i <= B; i++){
        factors.clear();
        factorize(i);
        if(isPrime(factors.size())) res++;
    }
    cout << res;
    return 0;
}