15,908,674 members
See more:
I solved a UVA problem: https://onlinejudge.org/external/131/13131.pdf[^]

My solution:
```void solve(Scanner sc, int n, int k) {
int sum=0;
for(int i=1; i<=n; i++) {
if(n%i==0 && i%k!=0)sum+=i;
}
System.out.println(sum);
}```

I got TLE in UVA. It was obvious to get TLE.

So, I tried to optimize my solution and implemented this way:
```void solve(Scanner sc, int n, int k) {
int sum=0;
for(int i=1; i*i<n; i++) {
if(n%i==0 && i%k!=0)sum+=i;
if(n%(n/i)==0 && (n/i)%k!=0)sum+=(n/i);
}
System.out.println(sum);
}```

But still I am getting TLE. To understand what's happening here I implemented the second approach in C++ and got accepted. But in Java I am getting TLE. I have no idea why is this happening and can't find out how to get ac. I am requesting you to help me solve the issue.. I am getting depressed, I love java, I don't want to shift in C++ for problem solving.

What I have tried:

Edit: Thanks to CPallini and Patrice T (See their answers and comments)
This is the last submitted solution. Improved the code but still getting TLE.
They both suggested to try a different approach "the list of prime factors of the number".
```//package pac1;
import java.util.Scanner;
public class Main{

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

int t = sc.nextInt();
while(t-->0) {
int n = sc.nextInt();
int k = sc.nextInt();
int sum=0;
int top = (int)Math.sqrt(n);
for(int i=1; i<=top; i++) {
if(n%i==0 ){
if(i%k!=0)sum+=i;
if((n/i)%k!=0)sum+=(n/i);
}
}
System.out.println(sum);
}

}
}```
Posted
Updated 9-Feb-23 14:34pm
v3

Solution 1

Try
Java
```static int solve(int n, int k)
{
int sum = 0;
int i;
for (i=1; i*i<n; ++i)
{
if ( n % i == 0)
{
if ( i % k != 0)
sum += i;

int j = n / i;
if ( j  % k != 0)
sum += j;
}
}
if ( i*i == n)
{
if ( i % k != 0)
sum += i;
}
return sum;
}
```

Note: your optimized solution is flawed: it adds twice to the sum the square root of `N`.

Jahirul Sarker 9-Feb-23 4:40am
"your optimized solution is flawed: it adds twice to the sum the square root of N." I edited the mistake.
I submitted your solution. But still getting TLE. @CPallini
CPallini 9-Feb-23 4:51am
Then you may try a different approach, for example maintaining a list of prime numbers.
Jahirul Sarker 9-Feb-23 5:13am
I searched in Google for the solution of this problem in Java, but found no results. A user asked on this same issue in UVA discussion site.. but no reply has been given.

I don't know how to solve this problem by maintaining a list of prime numbers.
Patrice T 9-Feb-23 16:47pm
+5
CPallini 10-Feb-23 4:18am
Thank you.

Solution 2

Quote:
I got TLE in UVA. It was obvious to get TLE.

This problem is worded the way of challenges sites, you need to know the strait forward solutions (or brute force) are never the solution.
You need to have deep understanding of the problem in order to apply algorithm simplifications and make your solution faster.
In this code, for any `N`, you loop `N` times: O(N)=N
Java
`for(int i=1; i<=n; i++) {`

In this code, for any `N`, you loop `√N` times: O(N)=√N
Java
`for(int i=1; i*i<n; i++) {`

But there is a multiplication on every loop.
In this code, `√N` multiplications are replace by a single square root function.
Java
```Top=int(sqrt(N)
for(int i=1; i<=Top; i++) {```

You need to take advantage of any possible shortcut in you code:
Everytime you find a divisor `i` of `N`, it imply that `N/I` is also a divisor of `N`, without further checking.
This code:
Java
```if(n%i==0 && i%k!=0)sum+=i;
if(n%(n/i)==0 && (n/i)%k!=0)sum+=(n/i);```

translate as
Java
```if(n%i==0 ){
if(i%k!=0)sum+=i;
if((n/i)%k!=0)sum+=(n/i);
}
And there is more to find.```

You also may want to play with the list of prime factors of the number.

v2
Jahirul Sarker 9-Feb-23 19:48pm
Thank you. But still TLE.
Last submitted solution:
```
//package pac1;
import java.util.Scanner;
public class Main{

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

int t = sc.nextInt();
while(t-->0) {
int n = sc.nextInt();
int k = sc.nextInt();
int sum=0;
int top = (int)Math.sqrt(n);
for(int i=1; i<=top; i++) {
if(n%i==0 ){
if(i%k!=0)sum+=i;
if((n/i)%k!=0)sum+=(n/i);
}
}
System.out.println(sum);
}

}
}
```
Patrice T 9-Feb-23 20:12pm
This change is just 1 step closer to solution. You need to do real study of the problem, and probably try different solutions

Use Improve question to update your question.
So that everyone can pay attention to this information.
Jahirul Sarker 9-Feb-23 20:38pm
I edited in "What have you tried" section.
CPallini 10-Feb-23 4:17am
5.
Patrice T 10-Feb-23 12:04pm
Hi, did you missed something ? :)