# Prime factorisation in java

I came across this question in a coding contest (Java-restricted) and I got TLE. I am unable to provide the link of the question as the contest is closed now. Can I know how can I optimise this?

Four Functions

Given four functions

• A(x) = Number of i where 1 <= i <= x and gcd(i,x) = 1
• B(x) = Sum of A(d) where d divides the number x
• C(x) = Sum of exponents of each prime in the prime factorization of B(x)
• D(x) = Sum of C(i) where 1 <= i <= x

If $$B(x) = {p_1} ^ {a1} {p_2} ^ {a2} {p_3} ^ {a3}$$ where p1,p2,p3 are prime factors of B(x), then C(x) is a1 + a2

Find the value of D(N) Constraints:

$$1 \le testcases \le 1000000$$

$$1 \le N \le 1000000$$

Example :

Input :

1

4

Output :

4

For n = 4

$$C(1) = 0$$

$$C(2) = 1$$

$$C(3) = 1$$

$$C(4) = 2$$

$$D(4) = C(1) + C(2) + C(3) + C(4) = 4$$

This is my approach

public class Main {
static long commonDivisor(long num1,long num2) {
if(num1 == 0) {
return num2;
}
return commonDivisor(num2 % num1, num1);
}

static long funcA(long numb) {
for (long itr = 2; itr * itr <= numb; itr++) {
if(numb % itr == 0) {
while(numb % itr == 0) {
numb /= itr;
}
}
}
if(numb > 1) {
}
}
static long funcB(long numb) {
long sum = 0;
for (long itr = 1; itr <= Math.sqrt(numb); itr++){
if (numb % itr == 0){
if(numb/itr == itr){
sum = sum + funcA(itr);
} else {
sum = sum + funcA(itr) + funcA(numb/itr);
}
}
}
return sum;
}
static boolean check_prime(long numb) {
BigInteger bigint = new BigInteger(String.valueOf(numb));
return bigint.isProbablePrime(1);
}
static long funcC(long numb) {
if (numb <= 1) {
return 0;
}
long remNum = numb;
long expo = 0;
for (long itr = 2; itr <= Math.sqrt(numb); itr++) {
if(check_prime(itr)) {
while (remNum % itr == 0) {
expo++;
remNum /= itr;
}
}
}
if(check_prime(remNum)) {
if (remNum > 1) {
expo++;
}
}
return expo;
}
static long funcD(long numb) {
long result = 0;
for(long itr = 1; itr <= numb; itr++){
result += funcC(funcB(itr));
}
return result;
}

public static void main(String[] args) {
try {
for(long itr = 1; itr <= testCases; itr++) {
System.out.println(funcD(number));
}
} catch(Exception e) {
System.out.println("Error");
}
}

• – D.W.
Apr 8, 2021 at 20:01

Function C can be improved by noting that the lowest divisor of a number is necessarily a prime, so calling check_prime is unnecessary. If itr was a * b then a and b would have been found first and divided out of remNum already, making itr not a divisor of remNum. The square root is also unnecessary, and relatively expensive. It can be avoided by testing itr * itr <= numb instead. There is no risk of overflow given that numb <= 1000000. Further refinements are possible.
Function D can be improved by caching the partial sums. In isolation that would not help, but there can be multiple test cases during a run of the program, and they can reuse the previously computed sums. For example as an extreme case, after the test case 1000000 has been used, any further test cases could be essentially free, because all possible cases would have been calculated at that point. Also, after funcD(10) has been evaluated, funcD(20) could start with that result instead of starting over from scratch.
• Just an addendum to the last part. The function $D$ can also be simplified. The function $C$ satisfies the logarithmic property $C(a)+C(b)=C(ab)$. Therefore $D(n)=C(n!)$. Now, $C(n!)$ can be computed using Legendre's formula by computing the primes up to $n$ and applying the formula to compute their exponents (or valuations) in the factorization of $n!$.