Sum of proper divisors

Question

Given a natural number \$n\$ (\$1 \le n \le 500000\$), please output the summation of all its proper divisors.

Definition: A proper divisor of a natural number is the divisor that is strictly less than the number.

e.g. number 20 has 5 proper divisors: 1, 2, 4, 5, 10, and the divisor summation is: 1 + 2 + 4 + 5 + 10 = 22.

Input

An integer stating the number of test cases (equal to about 200000), and that many lines follow, each containing one integer between 1 and 500000 inclusive.

Output

One integer each line: the divisor summation of the integer given respectively.

My solution:

It solved the problem in 1.63 seconds, which seems suboptimal considering its 3-second limit.

import java.util.ArrayList;
import java.util.Scanner;

public class Main
{
    public static void main(String[] args) {
        Scanner reader = new Scanner(System.in);
        int testcases = reader.nextInt();
        reader.nextLine();
        ArrayList<Integer> values = new ArrayList<Integer>();
        for(int i = 0; i<testcases; i++){
            values.add(reader.nextInt());
            reader.nextLine();
        }
        reader.close();
        for(int i = 0; i<testcases; i++){
            int sum = 1;
            int testcase = values.get(i);
            double lim = Math.sqrt(testcase);
            for(int k = 2; k<=lim; k++){
                if(testcase%k==0){
                    sum+=k;
                    int z = testcase/k;
                    if(k != z)
                        sum+=z;
                }
            }
            if(testcase==1)
                sum=0;
            if(i<testcases-1)
                System.out.println(sum);
            else
                System.out.print(sum);
        }
    }
}

---

EDIT: Updated code, which ran in a more respectable 0.22 seconds.

Taking out reader.nextLine(); improved the runtime by around 0.2 seconds.

Adding a special treatment to perfect squares seemed to have no noticable impact on speed (might depend on test cases?).

It turned out using BufferedReader and BufferedWriter had an immense impact on IO speed, reducing runtime to 0.22 seconds.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main
{
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        int testcases = Integer.parseInt(in.readLine());
        int[] values = new int[testcases];
        for(int i = 0; i<testcases; i++){
            values[i]=Integer.parseInt(in.readLine());
            }
        for(int i = 0; i<testcases; i++){
            int sum = 1;
            int testcase = values[i];
            double lim = Math.sqrt(testcase);
            for(int k = 2; k<lim; k++){
                if(testcase % k == 0){
                    sum += k + testcase / k;
                }
            }
            int intLim = (int) lim;
            if (intLim * intLim == testcase) {
                sum += lim;
            }
            if(testcase == 1)
                sum=0;
            out.write(sum + "\n");
        }
        out.flush();
    }
}

Answer 1

In the innermost for loop, you have a condition to check in every cycle if k is the square root. But most of the time it's not equal to the square root. It would be more optimal to rework that, and add a special treatment for square numbers once, after the loop:

for (int k = 2; k < lim; k++) {
    if (testcase % k == 0) {
        sum += k + testcase / k;
    }
}
int intLim = (int) lim;
if (intLim * intLim == testcase) {
    sum += lim;
}

---

You don't need the reader.nextLine() calls in this code, you can safely remove them. You can also remove the reader.close(), no need to close System.in.

int testcases = reader.nextInt();
//reader.nextLine();
List<Integer> values = new ArrayList<>();
for (int i = 0; i < testcases; i++) {
    values.add(reader.nextInt());
    //reader.nextLine();
}
//reader.close();

---

Is it really important to not print a newline at the end? If it's not important, then you can rewrite the loop as a for-each loop:

for (int testcase : values) {
    // ...
    System.out.println(sum);
}

---

Minor things:

• It's better to declare variables with interface types when possible, so instead of ArrayList<Integer> values = ..., use List<Integer> values = ...
• As of Java 7, use the diamond operator <> when creating parameterized types, for example List<Integer> values = new ArrayList<>()
• Always use braces even with single-statement if/else/for
• Put spaces around operators and parentheses, for example instead of if(testcase%k==0){ write as if (testcase % k == 0) {

Answer 2

        for(int i = 0; i<testcases; i++){
            int sum = 1;
            int testcase = values.get(i);

You never use i outside these three lines, so you could just as well write

        for (int testcase : values) {
            int sum = 1;

I would consider either renaming testcase to value, or renaming testcases to testcaseCount and values to testcases. I would prefer the latter, mostly because I prefer plural variable names to refer to collections.

Before that, you might want to add

        int lastValue = values.remove(values.size() - 1);

Then you can replace

            if(i<testcases-1)
                System.out.println(sum);
            else
                System.out.print(sum);

with just

            System.out.println(sum);

and handle the last value separately.