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();
    }
}

I'm learning algorithmic programming in Java. I wrote an algorithm for the following problem:

Given a natural number n (1 <= n <= 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.

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.