java - 完美数表现

Question

我有解决 Kattis 问题的方法 https://open.kattis.com/problems/almostperfect .解决方案被接受，但运行时间太长 (>1.00s)。 我尝试了一切来解决这个问题。我可以做些什么来进一步提高我的代码的性能？

import java.io.FileInputStream;
import java.util.Scanner;

import java.io.*;
import java.util.*;

public class almostperfect {

public static int perfect(int number){
    // 2 = perfect
    // 1 = almost perfect
    // 0 = not perfect
    int sum = 0;
    int b = 0;
    for(int i=1;i<number;i++)
    {
        if(number%i==0)
        {
            sum = sum + i;
        }
    }
    if(sum == number){
        b = 2;
    } else if(Math.abs(sum-number)<=2){
        b = 1;
    }

    return b;

}


public static void main(String[] args) 
{
    Scanner scan = new Scanner(System.in);
    ArrayList<Integer> input = new ArrayList<Integer>();
    int a;
    int status;
    while(scan.hasNextLong()){
        input.add((int) scan.nextLong());
    }
    for(int i=0; i<input.size(); i++){
    a = input.get(i);
    status = perfect(a);
    if(status==2){
        System.out.println(a+" perfect");
    } else if (status==1){
        System.out.println(a+" almost perfect");
    } else {
        System.out.println(a+" not perfect");
        }
    }

}}

Answer 1

当你计算number的除数时，你不必从1循环到number，而是循环到number的平方根>。以 100 为例 - 如果 2 是 100 的除数，则 100/2 也是。

int sum = 1;   //1 is always a divisor
int b = 0;
int sqr = (int)Math.sqrt(number);
for(int i=2;i< sqr;i++)
{
    if(number%i==0)
    {
        sum = sum + i;
        sum = sum + number/i;
    }
}
//Check what happens for sqr - if it's a divisor, add it only once
if (sqr * sqr == number)
    sum += sqr;