欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java实现的连续奇数(n+2*x)是合数的算法题暴力算法

程序员文章站 2024-02-28 16:40:40
连续6个奇数a,a+2,a+4,a+6,a+8,a+10都是合数,求最小的a的暴力解法。 先上结果,后面贴上代码: 1次连续n=9,连续值个数: 1;耗...

连续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

。。。。。。 后面的结果还没算出来

代码如下所示:

package com.test.test.zhihe;

import java.util.arraylist;
import java.util.hashmap;
import java.util.iterator;
import java.util.list;
import java.util.map;
import java.util.set;

/**
 * 连续6个奇数a,a+2,a+4,a+6,a+8,a+10都是合数,求最小的a
 */
public class zhishutest {
 /**
 * 判断某个数是否是合数. 相较于质数
 * @param num
 * @return
 */
 public static boolean he(int num){
 // 平方根
 int sq = ((double)math.sqrt(num)).intvalue();
 // 2 ...... sq
 for (int i = 2; i <= sq; i++) {
  int mo = num % i;
  if(0 == mo){
  return true;
  }
 }
 //
 return false;
 }

 /**
 * 主函数
 * @param args
 */
 public static void main(string[] args) {
 test();
 }
 public static void test() {
 // 开始时间
 long startmillis = system.currenttimemillis();
 // 上次完成时间
 long premillis = system.currenttimemillis();
 // 本次完成时间
 long curmillis = system.currenttimemillis();
 //
 int lianxu = 1000;
 int start = 1;
 int times = 1;
 for (int x = 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;
  }
  int size = 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()){
   integer key = iteratork.next(); // 次数
   integer value = map.get(key); // 最小n
   //
   // 本次完成时间
   curmillis = system.currenttimemillis();
   //
   long alltimeout = curmillis - startmillis;
   long curtimeout = 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();
 //
 long alltimeout = curmillis - startmillis;
 long curtimeout = curmillis - premillis;
 system.out.println("本次已经跑完了,下一个值超出了100次 " +
  ";无用耗时: " + curtimeout + "ms,总计: "+alltimeout+"ms");
 }
 
 
 /**
 * 
 * 测试 times 次的+2都是合数的最小n
 * @param times 计算次数
 * @param start 起始数字
 * @param onlystart 只计算单个start值.用于递归.外部调用应该传入
 * @return
 */
 public static list<map<integer, integer>> testtimeshe(int times,int start, boolean onlystart) {
 //
 list<map<integer, integer>> reslist= new arraylist<map<integer, integer>>();
 //
 // 防御式编程
 if(start < 1){
  return reslist;
 }
 if(0 == start % 2){ // 不处理偶数
  return reslist;
 }
 if(times < 1){
  times = 1;
 }
 //
 int result = -1;
 //
 for (int i = start; i < integer.max_value; i+=2) {
  //
  // 避免一直计算不返回
  if(onlystart && i > start){ // start 不满足,就直接
  return reslist;
  }
  for (int j = 0; j < times; j++) {
  int n = 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 = new hashmap<integer, integer>();
  resmap.put(times, result);
  reslist.add(resmap);
  // 尝试下一个次数,递归; 其实这个递归还可以继续优化一点; 贪婪算法,直接加下一次。。。
  // starttimes, 直接加这个参数。。。贪婪递归?
  // 多1次,从result这个数开始
  int t = times +1;
  int s = result;
  list<map<integer, integer>> nextlist = testtimeshe(t, s, true);
  // 如果有下一层的数字,则加入到当前结果
  if(null != nextlist && false==nextlist.isempty()){
   reslist.addall(nextlist);
  }
  
  //
  break;// 外层退出
  }
 }
 //
 return reslist;
 }
}

说明: 还有改进空间,欢迎下次修正