java 快速分解算法？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/6773462/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Fast factoring algorithms?
提问by fronthem
How can I quickly find all factors of a number?
如何快速找到一个数的所有因数？
e.g.:
例如：
digit: 20
factors: {1*20, 2*10, 4*5, 5*4, 10*2, 20*1}
位数：20个
因数：{1*20, 2*10, 4*5, 5*4, 10*2, 20*1}
回答by Patrick
This is actually a problem for which no good solution is known. For this reason, RSA encryption actually depends on the computational difficulty of factoring numbers. See: Integer Factorization
这实际上是一个没有好的解决方案的问题。为此，RSA 加密实际上取决于分解数字的计算难度。请参阅：整数分解
However, you may be able to speed up the algorithms already given by only looking at numbers up to the square root of n, and checking if they are factors by checking if n % i == 0. If this is true, you can find the corresponding factor greater than n^(.5)by taking n / i.
但是，您可以通过仅查看 的平方根以内的数字n并通过检查 if 来检查它们是否为因数来加速已经给出的算法n % i == 0。如果这是真的，您可以n^(.5)通过取找到大于 的相应因子n / i。
回答by Devon
If the number that you want to find the factors for happens to be odd, you only need to test odd numbers because it is impossible to have an even factor for an odd number. So with a pre-check up front, you can save yourself some processing.
如果您要为其求因数的数恰好是奇数，则只需测试奇数即可，因为奇数不可能有偶数因数。因此，通过预先进行预检查，您可以节省一些处理时间。
private static List<Integer> findFactors(int num)
{
int incrementer = 1;
if (num % 2 != 0)
{
incrementer = 2; //only test the odd ones
}
List<Integer> list = new ArrayList<Integer>();
for (int i = 1; i <= num / 2; i=i+incrementer)
{
if (num % i == 0)
{
list.add(i);
}
}
list.add(num);
return list;
}
回答by Edgar Velasquez Lim
Go through a loop applying modulus to all of the intermediate numbers.
循环对所有中间数应用模数。
X=1;
WHILE(X<=20)
IF 20%x == 0
THEN FACTOR!
X++;
END
回答by sgokhales
You probably wish to go for the modulus operator( % ).
您可能希望使用模运算符（ % ）。
E.g
例如
import java.util.Scanner;
public class Factor {
public static void main(String[] args) {
System.out.println("Enter a number whose factors are to be calculated: ");
Scanner scanNum = new Scanner(System.in);
int numFac = 0;
if(scanNum.hasNextInt()) {
numFac = scanNum.nextInt();
}
System.out.println("The Factors of the entered number are:-");
for(int i = 1; i <= numFac; i++) {
if(numFac%i == 0) {
System.out.print(i+" ");
}
}
}
}
回答by Eng.Fouad
public static Integer[] findFactors(int d)
{
List<Integer> list = new ArrayList<Integer>();
for(int i = 1; i <= d/2; i++)
{
if(d % i == 0) list.add(new Integer(i));
}
list.add(new Integer(d));
return (Integer[]) list.toArray(new Integer[0]);
}
public static void main(String[] args)
{
Integer[] list = findFactors(20);
for(Integer i : list) System.out.println(i);
}
Output:
输出：
1
2
4
5
10
20
回答by Nico Huysamen
List<Integer> factors = new ArrayList<Integer>();
for (int i = 1; i < NUMBER; i++) {
if (NUMBER % i == 0) {
factors.add(i);
}
}
回答by deepakl.2000
public class FactorGenerator{
private int number;
private int i;
public FactorGenerator(int numberToFactor){
number = numberToFactor;
}
public int nextFactor(){
while(number % i == 0){
System.out.print((Math.round(i)) + " ");
number =((number / i));
return i;
}
return i;
}
public boolean hasMoreFactors(){
for ( i = 2; i <= number; i++){
nextFactor();
}
return false;
}
}
}
Test Program:
import java.util.Scanner;
public class FactorgeneratorTester{
public static void main (String [] args){
Scanner in= new Scanner(System.in);
System.out.println("input the value");
int number = in.nextInt();
FactorGenerator fg = new FactorGenerator(number);
if (fg.hasMoreFactors()){
System.out.println(fg.hasMoreFactors());
}
}
}
}
the input
210
output
2 3 5 7
输入
210
输出
2 3 5 7
