The minimum cost of a path

You are given a 2D matrix containing $N$ rows and $M$ columns. You are currently standing at cell $(1,1)$ and you want to reach cell $(n,m)$.

You can only move right or down from your current cell, that is, if you are currently in cell $(i,j)$, then you can either move to cell $(i+1,j)$ or cell $(i,j+1)$. You cannot move out of the matrix.

Each cell of the grid has some cost associated with it which you have to pay when you land at that cell.

Each cell has a number $K$ associated with it. Now, the cost of that cell is defined as the maximum number of times you can divide $K$ by a positive integer $X$ that is greater than 1 until $K$ becomes 1. Here, $K$ must be divisible by $X$.

The cost of a path is defined as the sum of the costs of all the cells in the path.

Note: You also have to pay the cost at cell $(1,1)$ as you are standing on it.

You are required to determine the minimum cost to reach from cell $(1,1)$ to cell $(n,m)$.

Example:

Input:  n=2,m=2,2d[]={{1,3},{2,3}}
Output: 2

Approach

Java

public class MinCostPath {
    static int primes[];

    public static void main(String[] args) {
        sieve(500);
        // To store cost of every integer in the constraint range
        int cost_array[] = new int[100001];
        for (int i = 1; i < cost_array.length; i++) {
            cost_array[i] = get_cost(i);
        }
        int n = 2;
        int m = 2;
        int arr[][] = { { 1, 3 }, { 2, 3 } };
        int cost[][] = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cost[i][j] = cost_array[arr[i][j]];
            }
        }
        int ans = min_path_sum(cost, n, m);
        System.out.println(ans);
    }

    public static int get_cost(int val) {
        int lim = (int) (Math.sqrt(val)) + 1;
        int cnt = 0;
        for (int i = 0; i < primes.length && primes[i] <= lim; i++) {
            while (val % primes[i] == 0) {
                val /= primes[i];
                cnt++;
            }
        }
        if (val != 1) {
            cnt++;
        }
        return cnt;
    }

    // set false for prime number and true for composite number
    public static void sieve(int n) {
        boolean sieve[] = new boolean[n];
        primes = new int[95];
        int indx = 0;
        for (int i = 2; i < n; i++) {
            if (!sieve[i]) {
                primes[indx] = i;
                indx++;
                for (int j = 2; i * j < n; j++) {
                    sieve[i * j] = true;
                }
            }
        }
    }

    public static int min_path_sum(int arr[][], int n, int m) {
        int path_sum[][] = new int[n][m];
        path_sum[0][0] = arr[0][0];
        for (int i = 1; i < n; i++) {
            path_sum[i][0] = path_sum[i - 1][0] + arr[i][0];
        }

        for (int i = 1; i < m; i++) {
            path_sum[0][i] = path_sum[0][i - 1] + arr[0][i];
        }

        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                path_sum[i][j] = arr[i][j] + Math.min(path_sum[i - 1][j], path_sum[i][j - 1]);
            }
        }
        return path_sum[n - 1][m - 1];
    }
}