Here's my code. but it's TLE in test 5,7,8,9 help me?:

include

using namespace std;

// Get prime factors of a number vector getPrimeFactors(int n) { vector factors; for (int i = 2; i * i <= n; i++) { if (n % i == 0) { factors.push_back(i); while (n % i == 0) n /= i; } } if (n > 1) factors.push_back(n); return factors; }

// Dinic's Algorithm for Maximum Flow class Dinic { private: struct Edge { int to, cap, flow; };

vector<Edge> edges;
vector<vector<int>> adj;
vector<int> level, iter;
int n, source, sink;

bool bfs() {
    level.assign(n, -1);
    level[source] = 0;
    queue<int> q;
    q.push(source);

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int id : adj[v]) {
            if (level[edges[id].to] < 0 && edges[id].flow < edges[id].cap) {
                level[edges[id].to] = level[v] + 1;
                q.push(edges[id].to);
            }
        }
    }
    return level[sink] >= 0;
}

int dfs(int v, int pushed) {
    if (v == sink || pushed == 0) return pushed;

    for (int& cid = iter[v]; cid < adj[v].size(); cid++) {
        int id = adj[v][cid];
        int to = edges[id].to;

        if (level[v] + 1 != level[to] || edges[id].cap <= edges[id].flow)
            continue;

        int tr = dfs(to, min(pushed, edges[id].cap - edges[id].flow));
        if (tr > 0) {
            edges[id].flow += tr;
            edges[id ^ 1].flow -= tr;
            return tr;
        }
    }
    return 0;
}

public: Dinic(int n, int source, int sink) : n(n), source(source), sink(sink) { adj.resize(n); level.resize(n); iter.resize(n); }

void addEdge(int from, int to, int cap) {
    adj[from].push_back(edges.size());
    edges.push_back({to, cap, 0});
    adj[to].push_back(edges.size());
    edges.push_back({from, 0, 0});
}

int maxFlow() {
    int flow = 0;
    while (bfs()) {
        iter.assign(n, 0);
        while (int pushed = dfs(source, INT_MAX)) {
            flow += pushed;
        }
    }
    return flow;
}

};

int main() { ios_base::sync_with_stdio(false); cin.tie(NULL);

int n;
cin >> n;

vector<int> A(n), B(n);

for (int i = 0; i < n; i++) {
    cin >> A[i];
}

for (int i = 0; i < n; i++) {
    cin >> B[i];
}

// For small n, use simple approach
if (n <= 100) {
    // Simple bipartite matching
    vector<vector<bool>> canMatch(n, vector<bool>(n, false));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int g = __gcd(A[i], B[j]);
            if (g > 1) canMatch[i][j] = true;
        }
    }

    // Hungarian algorithm simulation with DFS
    vector<int> match(n, -1);
    int result = 0;

    for (int i = 0; i < n; i++) {
        vector<bool> used(n, false);
        function<bool(int)> dfs = [&](int v) -> bool {
            if (used[v]) return false;
            used[v] = true;

            for (int j = 0; j < n; j++) {
                if (canMatch[v][j] && (match[j] == -1 || dfs(match[j]))) {
                    match[j] = v;
                    return true;
                }
            }
            return false;
        };

        if (dfs(i)) result++;
    }

    cout << result << "\n";
    return 0;
}

// For large n, use optimized approach with prime factorization
map<int, int> primeToId;
int primeCount = 0;

// Get all prime factors from A and B
for (int x : A) {
    for (int p : getPrimeFactors(x)) {
        if (primeToId.find(p) == primeToId.end()) {
            primeToId[p] = primeCount++;
        }
    }
}

for (int x : B) {
    for (int p : getPrimeFactors(x)) {
        if (primeToId.find(p) == primeToId.end()) {
            primeToId[p] = primeCount++;
        }
    }
}

// Build flow network
// 0: source, 1..n: A vertices, n+1..2n: prime vertices, 2n+1..3n: B vertices, 3n+1: sink
int totalNodes = 3 * n + primeCount + 2;
int source = 0;
int sink = totalNodes - 1;

Dinic dinic(totalNodes, source, sink);

// Source to A vertices
for (int i = 0; i < n; i++) {
    dinic.addEdge(source, i + 1, 1);
}

// A vertices to prime vertices
for (int i = 0; i < n; i++) {
    for (int p : getPrimeFactors(A[i])) {
        int primeNode = n + 1 + primeToId[p];
        dinic.addEdge(i + 1, primeNode, 1);
    }
}

// Prime vertices to B vertices
for (int j = 0; j < n; j++) {
    for (int p : getPrimeFactors(B[j])) {
        int primeNode = n + 1 + primeToId[p];
        int bNode = n + 1 + primeCount + j;
        dinic.addEdge(primeNode, bNode, 1);
    }
}

// B vertices to sink
for (int j = 0; j < n; j++) {
    int bNode = n + 1 + primeCount + j;
    dinic.addEdge(bNode, sink, 1);
}

cout << dinic.maxFlow() << "\n";

return 0;

}