Java实现的连续奇数(n+2*x)是合数的算法题暴力算法
连续6个奇数a,a+2,a+4,a+6,a+8,a+10都是合数，求最小的a的暴力解法。
先上结果,后面贴上代码:
1次连续n=9,连续值个数:1;耗时:0ms,总计：0ms 2次连续n=25,连续值个数:1;耗时:0ms,总计：0ms 3次连续n=91,连续值个数:1;耗时:0ms,总计：0ms 4次连续n=115,连续值个数:3;耗时:0ms,总计：1ms 5次连续n=115,连续值个数:3;耗时:0ms,总计：1ms 6次连续n=115,连续值个数:3;耗时:0ms,总计：1ms 7次连续n=525,连续值个数:2;耗时:0ms,总计：1ms 8次连续n=525,连续值个数:2;耗时:0ms,总计：1ms 9次连续n=889,连续值个数:1;耗时:0ms,总计：1ms 10次连续n=1131,连续值个数:1;耗时:0ms,总计：1ms 11次连续n=1329,连续值个数:6;耗时:0ms,总计：1ms 12次连续n=1329,连续值个数:6;耗时:0ms,总计：1ms 13次连续n=1329,连续值个数:6;耗时:0ms,总计：1ms 14次连续n=1329,连续值个数:6;耗时:0ms,总计：1ms 15次连续n=1329,连续值个数:6;耗时:0ms,总计：1ms 16次连续n=1329,连续值个数:6;耗时:0ms,总计：1ms 17次连续n=9553,连续值个数:1;耗时:2ms,总计：3ms 18次连续n=15685,连续值个数:4;耗时:1ms,总计：5ms 19次连续n=15685,连续值个数:4;耗时:1ms,总计：5ms 20次连续n=15685,连续值个数:4;耗时:1ms,总计：5ms 21次连续n=15685,连续值个数:4;耗时:1ms,总计：5ms 22次连续n=19611,连续值个数:4;耗时:2ms,总计：8ms 23次连续n=19611,连续值个数:4;耗时:2ms,总计：8ms 24次连续n=19611,连续值个数:4;耗时:2ms,总计：8ms 25次连续n=19611,连续值个数:4;耗时:2ms,总计：8ms 26次连续n=31399,连续值个数:10;耗时:5ms,总计：13ms 27次连续n=31399,连续值个数:10;耗时:5ms,总计：13ms 28次连续n=31399,连续值个数:10;耗时:5ms,总计：13ms 29次连续n=31399,连续值个数:10;耗时:5ms,总计：13ms 30次连续n=31399,连续值个数:10;耗时:5ms,总计：13ms 31次连续n=31399,连续值个数:10;耗时:5ms,总计：13ms 32次连续n=31399,连续值个数:10;耗时:5ms,总计：13ms 33次连续n=31399,连续值个数:10;耗时:5ms,总计：13ms 34次连续n=31399,连续值个数:10;耗时:5ms,总计：13ms 35次连续n=31399,连续值个数:10;耗时:5ms,总计：13ms 36次连续n=155923,连续值个数:7;耗时:92ms,总计：105ms 37次连续n=155923,连续值个数:7;耗时:92ms,总计：105ms 38次连续n=155923,连续值个数:7;耗时:92ms,总计：105ms 39次连续n=155923,连续值个数:7;耗时:92ms,总计：105ms 40次连续n=155923,连续值个数:7;耗时:92ms,总计：105ms 41次连续n=155923,连续值个数:7;耗时:92ms,总计：105ms 42次连续n=155923,连续值个数:7;耗时:93ms,总计：106ms 43次连续n=360655,连续值个数:5;耗时:243ms,总计：349ms 44次连续n=360655,连续值个数:5;耗时:243ms,总计：349ms 45次连续n=360655,连续值个数:5;耗时:243ms,总计：349ms 46次连续n=360655,连续值个数:5;耗时:243ms,总计：349ms 47次连续n=360655,连续值个数:5;耗时:243ms,总计：349ms 48次连续n=370263,连续值个数:8;耗时:14ms,总计：363ms 49次连续n=370263,连续值个数:8;耗时:14ms,总计：363ms 50次连续n=370263,连续值个数:8;耗时:14ms,总计：363ms 51次连续n=370263,连续值个数:8;耗时:14ms,总计：363ms 52次连续n=370263,连续值个数:8;耗时:14ms,总计：363ms 53次连续n=370263,连续值个数:8;耗时:14ms,总计：363ms 54次连续n=370263,连续值个数:8;耗时:14ms,总计：363ms 55次连续n=370263,连续值个数:8;耗时:14ms,总计：363ms 56次连续n=492115,连续值个数:1;耗时:185ms,总计：548ms 57次连续n=1349535,连续值个数:2;耗时:1854ms,总计：2402ms 58次连续n=1349535,连续值个数:2;耗时:1854ms,总计：2402ms 59次连续n=1357203,连续值个数:7;耗时:22ms,总计：2424ms 60次连续n=1357203,连续值个数:7;耗时:22ms,总计：2424ms 61次连续n=1357203,连续值个数:7;耗时:22ms,总计：2424ms 62次连续n=1357203,连续值个数:7;耗时:22ms,总计：2424ms 63次连续n=1357203,连续值个数:7;耗时:22ms,总计：2424ms 64次连续n=1357203,连续值个数:7;耗时:22ms,总计：2424ms 65次连续n=1357203,连续值个数:7;耗时:22ms,总计：2424ms 66次连续n=2010735,连续值个数:8;耗时:1889ms,总计：4313ms 67次连续n=2010735,连续值个数:8;耗时:1889ms,总计：4313ms 68次连续n=2010735,连续值个数:8;耗时:1889ms,总计：4313ms 69次连续n=2010735,连续值个数:8;耗时:1889ms,总计：4313ms 70次连续n=2010735,连续值个数:8;耗时:1889ms,总计：4313ms 71次连续n=2010735,连续值个数:8;耗时:1889ms,总计：4313ms 72次连续n=2010735,连续值个数:8;耗时:1889ms,总计：4313ms 73次连续n=2010735,连续值个数:8;耗时:1890ms,总计：4314ms 74次连续n=4652355,连续值个数:3;耗时:10583ms,总计：14897ms 75次连续n=4652355,连续值个数:3;耗时:10583ms,总计：14897ms 76次连续n=4652355,连续值个数:3;耗时:10583ms,总计：14897ms 77次连续n=17051709,连续值个数:13;耗时:86082ms,总计：100979ms 78次连续n=17051709,连续值个数:13;耗时:86082ms,总计：100979ms 79次连续n=17051709,连续值个数:13;耗时:86082ms,总计：100979ms 80次连续n=17051709,连续值个数:13;耗时:86082ms,总计：100979ms 81次连续n=17051709,连续值个数:13;耗时:86082ms,总计：100979ms 82次连续n=17051709,连续值个数:13;耗时:86082ms,总计：100979ms 83次连续n=17051709,连续值个数:13;耗时:86082ms,总计：100979ms 84次连续n=17051709,连续值个数:13;耗时:86082ms,总计：100979ms 85次连续n=17051709,连续值个数:13;耗时:86083ms,总计：100980ms 86次连续n=17051709,连续值个数:13;耗时:86083ms,总计：100980ms 87次连续n=17051709,连续值个数:13;耗时:86083ms,总计：100980ms 88次连续n=17051709,连续值个数:13;耗时:86083ms,总计：100980ms 89次连续n=17051709,连续值个数:13;耗时:86083ms,总计：100980ms 90次连续n=20831325,连续值个数:15;耗时:34772ms,总计：135752ms 91次连续n=20831325,连续值个数:15;耗时:34772ms,总计：135752ms 92次连续n=20831325,连续值个数:15;耗时:34772ms,总计：135752ms 93次连续n=20831325,连续值个数:15;耗时:34772ms,总计：135752ms 94次连续n=20831325,连续值个数:15;耗时:34772ms,总计：135752ms 95次连续n=20831325,连续值个数:15;耗时:34772ms,总计：135752ms 96次连续n=20831325,连续值个数:15;耗时:34772ms,总计：135752ms 97次连续n=20831325,连续值个数:15;耗时:34772ms,总计：135752ms 98次连续n=20831325,连续值个数:15;耗时:34772ms,总计：135752ms 99次连续n=20831325,连续值个数:15;耗时:34773ms,总计：135753ms 100次连续n=20831325,连续值个数:15;耗时:34773ms,总计：135753ms 101次连续n=20831325,连续值个数:15;耗时:34773ms,总计：135753ms 102次连续n=20831325,连续值个数:15;耗时:34773ms,总计：135753ms 103次连续n=20831325,连续值个数:15;耗时:34773ms,总计：135753ms 104次连续n=20831325,连续值个数:15;耗时:34773ms,总计：135753ms 105次连续n=47326695,连续值个数:5;耗时:319130ms,总计：452155ms 106次连续n=47326695,连续值个数:5;耗时:319131ms,总计：452156ms 107次连续n=47326695,连续值个数:5;耗时:319131ms,总计：452156ms 108次连续n=47326695,连续值个数:5;耗时:319131ms,总计：452156ms 109次连续n=47326695,连续值个数:5;耗时:319131ms,总计：452156ms 110次连续n=122164749,连续值个数:1;耗时:1395200ms,总计：1847356ms 111次连续n=189695661,连续值个数:6;耗时:1705936ms,总计：3553292ms 112次连续n=189695661,连续值个数:6;耗时:1705936ms,总计：3553292ms 113次连续n=189695661,连续值个数:6;耗时:1705936ms,总计：3553292ms 114次连续n=189695661,连续值个数:6;耗时:1705936ms,总计：3553292ms 115次连续n=189695661,连续值个数:6;耗时:1705936ms,总计：3553292ms 116次连续n=189695661,连续值个数:6;耗时:1705936ms,总计：3553292ms 117次连续n=191912785,连续值个数:7;耗时:61964ms,总计：3615256ms 118次连续n=191912785,连续值个数:7;耗时:61964ms,总计：3615256ms 119次连续n=191912785,连续值个数:7;耗时:61964ms,总计：3615256ms 120次连续n=191912785,连续值个数:7;耗时:61964ms,总计：3615256ms 121次连续n=191912785,连续值个数:7;耗时:61964ms,总计：3615256ms 122次连续n=191912785,连续值个数:7;耗时:61964ms,总计：3615256ms 123次连续n=191912785,连续值个数:7;耗时:61964ms,总计：3615256ms 124次连续n=387096135,连续值个数:1;耗时:6650201ms,总计：10265457ms ----- 本次已经跑完了,下一个值超出了1000次;无用耗时:0ms,总计：xxxxxx135395ms
。。。。。。后面的结果还没算出来
代码如下所示:
packagecom.test.test.zhihe;
importjava.util.ArrayList;
importjava.util.HashMap;
importjava.util.Iterator;
importjava.util.List;
importjava.util.Map;
importjava.util.Set;
/**
*连续6个奇数a,a+2,a+4,a+6,a+8,a+10都是合数，求最小的a
*/
publicclassZhishuTest{
/**
*判断某个数是否是合数.相较于质数
*@paramnum
*@return
*/
publicstaticbooleanHe(intnum){
//平方根
intsq=((Double)Math.sqrt(num)).intValue();
//2......sq
for(inti=2;i<=sq;i++){
intmo=num%i;
if(0==mo){
returntrue;
}
}
//
returnfalse;
}
/**
*主函数
*@paramargs
*/
publicstaticvoidmain(String[]args){
test();
}
publicstaticvoidtest(){
//开始时间
longstartMillis=System.currentTimeMillis();
//上次完成时间
longpreMillis=System.currentTimeMillis();
//本次完成时间
longcurMillis=System.currentTimeMillis();
//
intlianxu=1000;
intstart=1;
inttimes=1;
for(intx=1;x<=lianxu;x++){
if(times>x){
continue;//跳过,进入下一次循环
}else{
times=x;
}
List<Map<Integer,Integer>>resList=testTimesHe(x,start,false);
//
//如果有数字,则进行处理
if(null==resList||resList.isEmpty()){
//找不到，就不会再有下一个了...
//深层嵌套太恶心了。。。
break;
}
intsize=resList.size();
//遍历
Iterator<Map<Integer,Integer>>iteratorR=resList.iterator();
while(iteratorR.hasNext()){
Map<Integer,Integer>map=(Map<Integer,Integer>)iteratorR.next();
//
if(null!=map&&!map.isEmpty()){
//Map遍历太恶心了.烂Java
Set<Integer>keys=map.keySet();
Iterator<Integer>iteratorK=keys.iterator();
if(iteratorK.hasNext()){
Integerkey=iteratorK.next();//次数
Integervalue=map.get(key);//最小n
//
//本次完成时间
curMillis=System.currentTimeMillis();
//
longallTimeout=curMillis-startMillis;
longcurTimeout=curMillis-preMillis;
System.out.println(""+key+"次连续n="+value+",连续值个数:"+size+
";耗时:"+curTimeout+"ms,总计："+allTimeout+"ms");
//处理数据,贪婪处理过的就不处理了
if(key>0&&value>0){
times=key+1;
start=value;
}
}
}
}
//计入上次完成时间
preMillis=System.currentTimeMillis();
}
//
//本次完成时间
curMillis=System.currentTimeMillis();
//
longallTimeout=curMillis-startMillis;
longcurTimeout=curMillis-preMillis;
System.out.println("本次已经跑完了,下一个值超出了100次"+
";无用耗时:"+curTimeout+"ms,总计："+allTimeout+"ms");
}
/**
*
*测试times次的+2都是合数的最小n
*@paramtimes计算次数
*@paramstart起始数字
*@paramonlyStart只计算单个start值.用于递归.外部调用应该传入
*@return
*/
publicstaticList<Map<Integer,Integer>>testTimesHe(inttimes,intstart,booleanonlyStart){
//
List<Map<Integer,Integer>>resList=newArrayList<Map<Integer,Integer>>();
//
//防御式编程
if(start<1){
returnresList;
}
if(0==start%2){//不处理偶数
returnresList;
}
if(times<1){
times=1;
}
//
intresult=-1;
//
for(inti=start;i<Integer.MAX_VALUE;i+=2){
//
//避免一直计算不返回
if(onlyStart&&i>start){//start不满足,就直接
returnresList;
}
for(intj=0;j<times;j++){
intn=i+2*j;
//
if(!He(n)){
break;//内层退出
}
//
if(j+1==times){
//跑到结果了.times次都满足
result=i;
break;//这里退不退无所谓,跑到for的最后了
}
}
//
if(result>0){
//
//System.out.println("result="+result);
//
Map<Integer,Integer>resMap=newHashMap<Integer,Integer>();
resMap.put(times,result);
resList.add(resMap);
//尝试下一个次数,递归;其实这个递归还可以继续优化一点;贪婪算法,直接加下一次。。。
//startTimes,直接加这个参数。。。贪婪递归?
//多1次,从result这个数开始
intt=times+1;
ints=result;
List<Map<Integer,Integer>>nextList=testTimesHe(t,s,true);
//如果有下一层的数字,则加入到当前结果
if(null!=nextList&&false==nextList.isEmpty()){
resList.addAll(nextList);
}
//
break;//外层退出
}
}
//
returnresList;
}
}
说明：还有改进空间,欢迎下次修正