服务器之家

服务器之家 > 正文

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

时间:2019-11-28 14:18     来源/作者:junjie

连续6个奇数a,a+2,a+4,a+6,a+8,a+10都是合数,求最小的a的暴力解法。

先上结果,后面贴上代码:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
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

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

代码如下所示:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
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;
 }
}

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

相关文章

热门资讯

玄元剑仙肉身有什么用 玄元剑仙肉身境界等级划分
玄元剑仙肉身有什么用 玄元剑仙肉身境界等级划分 2019-06-21
男生常说24816是什么意思?女生说13579是什么意思?
男生常说24816是什么意思?女生说13579是什么意思? 2019-09-17
配置IIS网站web服务器的安全策略配置解决方案
配置IIS网站web服务器的安全策略配置解决方案 2019-05-23
Nginx服务器究竟是怎么执行PHP项目
Nginx服务器究竟是怎么执行PHP项目 2019-05-24
华为nova5pro和p30pro哪个好 华为nova5pro和华为p30pro对比详情
华为nova5pro和p30pro哪个好 华为nova5pro和华为p30pro对比详情 2019-06-22
返回顶部