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; } }
说明:还有改进空间,欢迎下次修正