我会怎么做:
- 开始在999,向后工作我的方式,以998,997,等
- 创建我目前的数字回文。
- 确定此数字的素数因子分解(如果您有预先生成的素数列表,则并非全部昂贵)
- 通过此素数因子分解列表来确定是否可以使用这些因子的组合来制作2 3位数
一些代码:。
int[] primes = new int[] {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,
73,79,83,89,97,101,103,107,109,113,,127,131,137,139,149,151,157,163,167,173,
179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,
283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,
419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,
547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,
661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,
811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,
947,953,967,971,977,983,991,997};
for(int i = 999; i >= 100; i--) {
String palstr = String.valueOf(i) + (new StringBuilder().append(i).reverse());
int pal = Integer.parseInt(pal);
int[] factors = new int[20]; // cannot have more than 20 factors
int remainder = pal;
int facpos = 0;
primeloop:
for(int p = 0; p < primes.length; i++) {
while(remainder % p == 0) {
factors[facpos++] = p;
remainder /= p;
if(remainder < p) break primeloop;
}
}
// now to do the combinations here
}
当然,你可以更优化它,你可以做在纸张上一些自己的数学削减搜索空间。这就成了一个问题,设置任务的人愿意接受什么,因为问题只有一个正确的答案,而打印该数字的最佳方式就是将其作为字符串放在源代码中。一个相关的概念是决定一个数是否为素数,并产生一个*证明*,它是主要的。 –
@Steve Jessop,你能举一些这个问题的代码.. – ferhan
例如,一个程序,只是'System.out.println(“906609”);'功能上等价于你(证明不适合这个边际),毫无疑问更快。当然,这是削减搜索空间的一个极端例子。由于任何可被100除尽的结果都在'00'结束,因此不是回文,因此起始于101而不是100作为较低的循环界限而具有极小的性能增益。你必须自己决定在那个范围内你做了“太多”的数学证明,没有足够的数字处理。 –