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

简介: // 连续6个奇数a,a+2,a+4,a+6,a+8,a+10都是合数,求最小的a// 暴力解法先上结果,后面贴上代码:1次连续n=9,连续值个数: 1;耗时: 0ms,总计: 0ms2次连续n=25,连续值个数: 1;耗时: 0ms,总计: 0ms3次连续n=91,连续值个数: 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
125次连续n=436273011,连续值个数: 16;耗时: 1999567ms,总计: 12265024ms
126次连续n=436273011,连续值个数: 16;耗时: 1999567ms,总计: 12265024ms
127次连续n=436273011,连续值个数: 16;耗时: 1999567ms,总计: 12265024ms
128次连续n=436273011,连续值个数: 16;耗时: 1999567ms,总计: 12265024ms
129次连续n=436273011,连续值个数: 16;耗时: 1999567ms,总计: 12265024ms
130次连续n=436273011,连续值个数: 16;耗时: 1999567ms,总计: 12265024ms
131次连续n=436273011,连续值个数: 16;耗时: 1999567ms,总计: 12265024ms
132次连续n=436273011,连续值个数: 16;耗时: 1999567ms,总计: 12265024ms
133次连续n=436273011,连续值个数: 16;耗时: 1999567ms,总计: 12265024ms
134次连续n=436273011,连续值个数: 16;耗时: 1999567ms,总计: 12265024ms
135次连续n=436273011,连续值个数: 16;耗时: 1999568ms,总计: 12265025ms
136次连续n=436273011,连续值个数: 16;耗时: 1999568ms,总计: 12265025ms
137次连续n=436273011,连续值个数: 16;耗时: 1999568ms,总计: 12265025ms
138次连续n=436273011,连续值个数: 16;耗时: 1999568ms,总计: 12265025ms
139次连续n=436273011,连续值个数: 16;耗时: 1999568ms,总计: 12265025ms
140次连续n=436273011,连续值个数: 16;耗时: 1999568ms,总计: 12265025ms
141次连续n=1294268493,连续值个数: 3;耗时: 49257124ms,总计: 61522149ms
142次连续n=1294268493,连续值个数: 3;耗时: 49257124ms,总计: 61522149ms
143次连续n=1294268493,连续值个数: 3;耗时: 49257124ms,总计: 61522149ms
144次连续n=1453168143,连续值个数: 2;耗时: 11962769ms,总计: 73484918ms
145次连续n=1453168143,连续值个数: 2;耗时: 11962769ms,总计: 73484918ms

.....
----- 
本次已经跑完了,下一个值超出了1000次;无用耗时: 0ms,总计: xxxxxx135395ms
。。。。。。 后面的结果还没算出来,相比看到这里你就发现多线程的好处了。。。 单线程在4核心的CPU上也只有25%的利用率。

代码如下所示:

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
 * @author http://blog.csdn.net/renfufei
 */
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;
	}
}


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

目录
相关文章
|
前端开发 算法 JavaScript
LeetCode生成每种字符都是奇数个的字符串使用JavaScript解题|前端学算法
LeetCode生成每种字符都是奇数个的字符串使用JavaScript解题|前端学算法
87 0
LeetCode生成每种字符都是奇数个的字符串使用JavaScript解题|前端学算法
|
Rust 算法 安全
【算法学习】1588. 所有奇数长度子数组的和(java / c / c++ / python / go / rust)
给你一个正整数数组 arr ,请你计算所有可能的奇数长度子数组的和。 子数组 定义为原数组中的一个连续子序列。 请你返回 arr 中 所有奇数长度子数组的和 。
【算法学习】1588. 所有奇数长度子数组的和(java / c / c++ / python / go / rust)
|
算法 C语言
【算法与数据结构】奇数阶魔方阵
【算法与数据结构】奇数阶魔方阵
195 0
|
算法 C语言
空瓶换水喝水问题?给一个数组,如何让奇数在前偶数在后?C语言从入门到入土(进阶篇)(算法篇p5)
题一:喝水问题,一块钱可以换1瓶水,2个空瓶可以换1瓶水,给你对应的钱数求能喝的水数:
|
2天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于GA遗传优化的GroupCNN分组卷积网络时间序列预测算法matlab仿真
该算法结合了遗传算法(GA)与分组卷积神经网络(GroupCNN),利用GA优化GroupCNN的网络结构和超参数,提升时间序列预测精度与效率。遗传算法通过模拟自然选择过程中的选择、交叉和变异操作寻找最优解;分组卷积则有效减少了计算成本和参数数量。本项目使用MATLAB2022A实现,并提供完整代码及视频教程。注意:展示图含水印,完整程序运行无水印。
|
1天前
|
算法 决策智能
基于禁忌搜索算法的VRP问题求解matlab仿真,带GUI界面,可设置参数
该程序基于禁忌搜索算法求解车辆路径问题(VRP),使用MATLAB2022a版本实现,并带有GUI界面。用户可通过界面设置参数并查看结果。禁忌搜索算法通过迭代改进当前解,并利用记忆机制避免陷入局部最优。程序包含初始化、定义邻域结构、设置禁忌列表等步骤,最终输出最优路径和相关数据图表。
|
2天前
|
编解码 算法 数据挖掘
基于MUSIC算法的六阵元圆阵DOA估计matlab仿真
该程序使用MATLAB 2022a版本实现基于MUSIC算法的六阵元圆阵DOA估计仿真。MUSIC算法通过区分信号和噪声子空间,利用协方差矩阵的特征向量估计信号到达方向。程序计算了不同角度下的MUSIC谱,并绘制了三维谱图及对数谱图,展示了高分辨率的DOA估计结果。适用于各种形状的麦克风阵列,尤其在声源定位中表现出色。
|
8天前
|
传感器 算法 C语言
基于无线传感器网络的节点分簇算法matlab仿真
该程序对传感器网络进行分簇,考虑节点能量状态、拓扑位置及孤立节点等因素。相较于LEACH算法,本程序评估网络持续时间、节点死亡趋势及能量消耗。使用MATLAB 2022a版本运行,展示了节点能量管理优化及网络生命周期延长的效果。通过簇头管理和数据融合,实现了能量高效和网络可扩展性。
|
2天前
|
数据采集 算法 5G
基于稀疏CoSaMP算法的大规模MIMO信道估计matlab性能仿真,对比LS,OMP,MOMP,CoSaMP
该研究采用MATLAB 2022a仿真大规模MIMO系统中的信道估计,利用压缩感知技术克服传统方法的高开销问题。在稀疏信号恢复理论基础上,通过CoSaMP等算法实现高效信道估计。核心程序对比了LS、OMP、NOMP及CoSaMP等多种算法的均方误差(MSE),验证其在不同信噪比下的性能。仿真结果显示,稀疏CoSaMP表现优异。
9 2