完美數字性能

我有一個解決方案，爲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"); 
     } 
    } 

}}

來源

2016-11-01 Valakor

提示：如果'i'是'number'的一個因子，那麼'number/i'也是。 – Henry

另外，運行你的for循環，直到'我 rafid059

不要一路走到數字。數字不會有任何因素>數字/ 2。 – nicomp

當你計算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;

來源

2016-11-01 17:35:35 TDG

你的代碼很好，不好的是找到它實現的數字的因子的方法。你需要比蠻力檢查更智能每可能的數字小於數字，如果它是一個因素。

首先，明顯是1是總是一個因素，因爲任何數字除以1而沒有餘數。而且，根據定義，數字本身不是一個因素。這限制了在範圍（2 ... n-1）中找到的因素。

其次，如果你找到一個除數，那麼，股息也是一個除數：

dividend = number/divisor -> implies: dividend is also a divisor

這意味着除數總是在對發現（分紅也是一個除數，使得對）。必須考慮的一個例外是，股息可能與股息相同（例如，數字= 9，除數= 3 - >股息= 3）。這可以被利用，導致：

第三，當從可能的最小除數（2）開始測試時，您發現的第一個紅利是可能的最大除數，當增加測試除數時紅利穩步下降。這意味着沒有必要明確檢查被發現爲股息的除數。這意味着測試上限將是除數和紅利相等的地方，換句話說就是數字的根源。

正如鏈接中的問題所述，數字可能在1 ... 1E9的範圍內。你的蠻力方法需要1E9的1億次測試，而使用上述屬性的智能版本只需要31621.這大約快30000倍！

來源

2016-11-01 18:42:58 Durandal

完美數字性能

回答

相關問題