查找假數的所有因子

我正在嘗試查找最快的全因子算法。我使用把所有因素放入一個數組列表中進行添加，並將其與原始數字進行比較，以確定它們是否相同。查找假數的所有因子

示例。如果你加1 + 2 + 3 = 6，6的因子是[1,2,3}。

除了我現在的程序之外，還有更快的方法來分解，添加和比較嗎？

public class Phony_Number { 

private int number; 

public Phony_Number(int num) { 
    number = num; 
    print(); 
} 

public Phony_Number() { 
    number = 0; 
} 

private ArrayList<Integer> factoring(int num) { 
    ArrayList<Integer> factors = new ArrayList<Integer>(); 
    if (num % 2 == 0) { 
     for (int ff = 3; ff < num; ff++) { 
      if (num % ff == 0) { 
       factors.add(ff); 
      } 
     } 
    } 
    return factors; 
} 

private int sum(ArrayList<Integer> array) { 
    int sum = 0; 
    for (int i = 0; i < array.size(); i++) { 
     sum = +sum + array.get(i); 
    } 
    return sum+3; 
} 

private boolean compare(int num, int sum) { 
    if (num == sum) 
     return true; 
    return false; 
} 

public void print() { 
    for (int i = number; i > 5; i--) { 
     if (compare(i, sum(factoring(i)))) { 
      System.out.println("Number " + i + " is phony number"); 
     } 
    } 
}

}

My current result for 20,000 numbers is this 

Number 8128 is phony number 

Number 496 is phony number 

Number 28 is phony number 

Number 6 is phony number 

Nano RunTime 359624716

來源

2014-09-04 Neoaptt

這是一個項目歐拉問題？ – wvdz 2014-09-04 15:00:21

順便說一句，你只是分解偶數（你確定Phony Numbers都是偶數？）。你可以篩分直到「Sqrt（Limit）」，將數字素數分解並使用素數因子分解生成除數。也可以在素數中添加因式分解緩存。 – NetVipeC 2014-09-04 15:33:21

這些數字被稱爲完美數字，而不是假數字，你可以通過搜索整數序列的在線百科全書來找到6,28,496,8128。唯一的完美數字的形式是2 * 2^n *（2^n-1）其中2^n-1是素數，它是一個着名的開放問題，是否存在奇數的完美數字，並且您不會通過小數字的蠻力搜索找到任何數字。對數字進行因子分解的方法要比試驗分部快得多，或者甚至是測試可能的素數因子至sqrt（n）的更好方法，但其中很多都是複雜的。例如，嘗試Pollard-rho因子分解。 – 2014-09-04 17:27:23

幾件小事跳了出來：你比較的方法是沒有意義的，刪除它將簡化你的代碼一點點。你的總和方法可以使用+ =。爲什麼循環遍歷每個數字，然後放下其中的一半，只需在循環中使用 - = 2。

您的主要儲蓄雖然可以來自您的factoring方法 - 您知道num/2以上的數字不能成爲因素，因此只要您到達那裏，您就可以停下來。

（事實上，在這種情況下，你可以停在num/3因爲你跳過2

來源

2014-09-04 14:47:52

當你通過迭代我相信你可以做師取得共同的因素，以及對於例如：

if (num % ff == 0) 
{ 
    factors.add(num/ff) 
    factors.add(ff); 
}

但你必須考慮到已經加入他們，所以我還不能肯定它是否有助於從長遠來看

您還可以使用：

return num == sum

來源

2014-09-04 14:53:18 FintanH

num的除數ff成對出現，即如果ff是除數，則ff和num/ff都是除數。此外，除非ff * ff == num，否則該對中的除數是不同的。所以你改變你的循環條件爲ff * ff < = num，然後如果ff除num，則將ff加到因子列表中，並且如果ff * ff！= num，則添加num/ff。這將使您的程序以num時間的平方根運行，而不是num時間。

來源

2014-09-04 16:14:09 user2566092

查找假數的所有因子

回答

相關問題