快速分解算法?
如何快速查找数字的所有因子?
例如:
数字:20
因素:{1 * 20,2 * 10,4 * 5,5 * 4,10 * 2,20 * 1}
这实际上是一个尚未知道好解决方案的问题。 因此,RSA加密实际上取决于分解数字的计算难度。 请参阅: 整数分解
但是,您可以通过查看直到n
平方根的数字来加速已经给出的算法,并通过检查n % i == 0
来检查它们是否是因子。 如果这是真的,你可以通过取n / i
找到大于n^(.5)
的相应因子。
如果要查找因子的数字恰好是奇数,则只需要测试奇数,因为对于奇数不可能有偶数因子。 因此,通过预先检查,您可以节省一些处理。
private static List findFactors(int num) { int incrementer = 1; if (num % 2 != 0) { incrementer = 2; //only test the odd ones } List list = new ArrayList (); for (int i = 1; i <= num / 2; i=i+incrementer) { if (num % i == 0) { list.add(i); } } list.add(num); return list; }
通过将模数应用于所有中间数的循环。
X=1; WHILE(X<=20) IF 20%x == 0 THEN FACTOR! X++; END
您可能希望使用模数运算符(%)。
例如
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+" "); } } } }
List factors = new ArrayList (); for (int i = 1; i < NUMBER; i++) { if (NUMBER % i == 0) { factors.add(i); } }
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()); } }
}
输入
210
产量
2 3 5 7
public static Integer[] findFactors(int d) { List list = new ArrayList (); 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); }
输出:
1 2 4 5 10 20