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

• Kenney: I tested this locally, and most of the time is due to IO: running in Eclipse with 200.000 random numbers (producing 6.2MB output) it takes 4.7 seconds, on the commandline 2.9 seconds, and on the commandline redirecting stdout to a file it takes 1 second. Without printing any output the algorithm takes 120ms.
• user3050748: @Kenney Interesting. How could I decrease IO time?
• Kenney: I tried buffering all output and do a System.out.write but that doesn't speed things up. The only way that I know is to output to a file instead of stdout, as this bypasses the OS rendering terminals and such. Btw, your algorithm will miss some output: for example sqrt(20) is about 4.47 so you will miss divisors 5 and 10.
• Andreas: This may not have a big impact, but Scanner is a beast, performance-wise. Use a BufferedReader and Integer.parseInt(). --- Also, you are wasting time building an ArrayList<Integer>, boxing all the values and building up the list. Just perform your logic as you read the values. --- You should move the inside of the for loop to a method that returns the sum, and print in the caller. This will allow adding unit tests to your code, and isolates the logic from the I/O, for a better structured program.
• user3050748: @Andreas using BufferedReader and BufferedWriter indeed had quite a big impact on IO speed. The code ran in 0.22 seconds. I also used an integer array instead of an ArrayList.

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.