Six consecutive odd numbers a, a+2, a+4, a+6, a+8, a+10 are all composite numbers. Find the brute force solution for the smallest a.
Post the results first, then paste the code:
1 consecutive n=9, number of consecutive values: 1; time consuming: 0ms, total: 0ms 2 consecutive times n=25, number of consecutive values: 1; time consuming: 0ms, total: 0ms 3 consecutive times n=91, consecutive Number of values: 1; Time consuming: 0ms, Total: 0ms 4 consecutive times n=115, Number of consecutive values: 3; Time consuming: 0ms, Total: 1ms 5 consecutive n=115, number of consecutive values: 3; time consumption: 0ms, total: 1ms 6 consecutive times n=115, number of consecutive values: 3; time consuming: 0ms, total: 1ms 7 consecutive n=525, continuous Number of values: 2; Time consuming: 0ms, Total: 1ms 8 consecutive times n=525, Number of consecutive values: 2; Time consuming: 0ms, Total: 1ms 9 consecutive times n=889, number of consecutive values: 1; time consuming: 0ms, total: 1ms 10 consecutive times n=1131, number of consecutive values: 1; time consuming: 0ms, total: 1ms 11 times consecutive n=1329, continuous Number of values: 6; Time consuming: 0ms, Total: 1ms12 consecutive times n=1329, Number of consecutive values: 6; Time consuming: 0ms, Total: 1ms 13 consecutive times n=1329, number of consecutive values: 6; time consumption: 0ms, total: 1ms 14 times consecutive n=1329, number of consecutive values: 6; time consumption: 0ms, total: 1ms 15 times consecutive n=1329, consecutive Number of values: 6; Time consuming: 0ms, Total: 1ms16 consecutive times n=1329, Number of consecutive values: 6; Time consuming: 0ms, total: 1ms, 17 consecutive times n=9553, number of consecutive values: 1; time consuming: 2ms, total: 3ms, 18 consecutive times n=15685, number of consecutive values: 4; time consuming: 1ms, total: 5ms, 19 consecutive times n =15685, number of consecutive values: 4; time consumption: 1ms, total: 5ms20 times consecutive n=15685, number of consecutive values: 4; Time consuming: 1ms, total: 5ms, 21 consecutive times n=15685, number of consecutive values: 4; Time consuming: 1ms, total: 5ms, 22 consecutive times n=19611, number of consecutive values: 4; Time consuming: 2ms, total : 8ms23 consecutive times n=19611, number of consecutive values: 4; time consuming: 2ms, total: 8ms24 consecutive times n=19611, number of consecutive values: 4; time consumption: 2ms, total: 8ms25 consecutive times n=19611, number of consecutive values: 4; time consumption: 2ms, total number: 8ms26 consecutive times n=31399, consecutive Number of values: 10; time consuming: 5ms, total: 13ms, 27 consecutive times n=31399, number of consecutive values: 10; Time consuming: 5ms, total: 13ms, 28 consecutive times n=31399, number of consecutive values: 10; Time consuming: 5ms, total: 13ms, 29 consecutive times n=31399, number of consecutive values: 10; Time consuming: 5ms, total : 13ms30 consecutive times n=31399, number of consecutive values: 10; time consuming: 5ms, total: 13ms31 consecutive times n=31399, number of consecutive values: 10; time consumption: 5ms, total: 13ms32 consecutive times n=31399, number of consecutive values: 10; time consumption: 5ms, total number: 13ms33 times consecutive n=31399, consecutive Number of values: 10; time consumption: 5ms, total: 13ms34 consecutive times n=31399, number of consecutive values: 10; time consuming: 5ms, total: 13ms35 consecutive times n=31399, number of consecutive values: 10; time consuming: 5ms, total: 13ms36 times consecutive n=155923, consecutive Number of values: 7; Time taken: 92ms, Total: 105ms37 consecutive times n=155923, number of consecutive values: 7; time consuming: 92ms, total: 105ms38 consecutive times n=155923, number of consecutive values: 7; time consuming: 92ms, total: 105ms39 times consecutive n=155923, consecutive Number of values: 7; Time taken: 92ms, Total: 105ms40 consecutive times n=155923, number of consecutive values: 7; time consuming: 92ms, total: 105ms41 consecutive times n=155923, number of consecutive values: 7; time consuming: 92ms, total: 105ms42 times consecutive n=155923, consecutive Number of values: 7; time taken: 93ms, total: 106ms43 consecutive times n=360655, number of consecutive values: 5; time consumption: 243ms, total: 349ms44 consecutive times n=360655, number of consecutive values: 5; time consumption: 243ms, total number: 349ms45 times consecutive n=360655, continuous Number of values: 5; time consumption: 243ms, total: 349ms46 consecutive times n=360655, number of consecutive values: 5; time consumption: 243ms, total: 349ms47 consecutive times n=360655, number of consecutive values: 5; time consumption: 243ms, total number: 349ms48 times consecutive n=370263, continuous Number of values: 8; Time taken: 14ms, Total: 363ms49 times consecutive n=370263, number of consecutive values: 8; time consuming: 14ms, total: 363ms50 times consecutive n=370263, number of consecutive values: 8; time consuming: 14ms, total: 363ms51 times consecutive n=370263, continuous Number of values: 8; Time taken: 14ms, Total: 363ms52 consecutive times n=370263, number of consecutive values: 8; time consuming: 14ms, total: 363ms53 consecutive times n=370263, number of consecutive values: 8; time consuming: 14ms, total: 363ms54 times consecutive n=370263, continuous Number of values: 8; Time taken: 14ms, Total: 363ms55 consecutive times n=370263, number of consecutive values: 8; time consuming: 14ms, total: 363ms56 times consecutive n=492115, number of consecutive values: 1; time consuming: 185ms, total: 548ms57 times consecutive n=1349535, continuous Number of values: 2; time consuming: 1854ms, total: 2402ms58 consecutive times n=1349535, number of consecutive values: 2; time consumption: 1854ms, total: 2402ms59 consecutive times n=1357203, number of consecutive values: 7; time consumption: 22ms, total number: 2424ms60 times consecutive n=1357203, consecutive Number of values: 7; time consumption: 22ms, total: 2424ms61 consecutive times n=1357203, number of consecutive values: 7; time consumption: 22ms, total: 2424ms62 consecutive times n=1357203, number of consecutive values: 7; time consumption: 22ms, total number: 2424ms63 consecutive times n=1357203, consecutive Number of values: 7; time consumption: 22ms, total: 2424ms64 consecutive times n=1357203, number of consecutive values: 7; time consumption: 22ms, total: 2424ms65 consecutive times n=1357203, number of consecutive values: 7; time consumption: 22ms, total number: 2424ms66 consecutive times n=2010735, continuous Number of values: 8; Time taken: 1889ms, Total: 4313ms67 consecutive times n=2010735, number of consecutive values: 8; time consumption: 1889ms, total: 4313ms68 consecutive times n=2010735, number of consecutive values: 8; time consumption: 1889ms, total number: 4313ms69 times consecutive n=2010735, consecutive Number of values: 8; Time taken: 1889ms, Total: 4313ms70 consecutive times n=2010735, number of consecutive values: 8; time consuming: 1889ms, total: 4313ms71 consecutive times n=2010735, number of consecutive values: 8; time consuming: 1889ms, total: 4313ms72 consecutive times n=2010735, consecutive Number of values: 8; Time taken: 1889ms, Total: 4313ms73 consecutive times n=2010735, number of consecutive values: 8; time consumption: 1890ms, total: 4314ms74 consecutive times n=4652355, number of consecutive values: 3; time consumption: 10583ms, total number: 14897ms75 consecutive times n=4652355, consecutive Number of values: 3; Time taken: 10583ms, total: 14897ms76 consecutive times n=4652355, number of consecutive values: 3; time consumption: 10583ms, total: 14897ms77 times consecutive n=17051709, number of consecutive values: 13; time consumption: 86082ms, total number: 100979ms78 consecutive times n=17051709, number of consecutive values: 13; time consuming: 86082ms, total: 100979ms79 consecutive times n=17051709, number of consecutive values: 13; time consuming: 86082ms, total: 100979ms80 times consecutive n=17051709, consecutive Number of values: 13; Time consuming: 86082ms, total: 100979ms81 times consecutive n=17051709, number of consecutive values: 13; Time consuming: 86082ms, total: 100979ms82 times consecutive n=17051709, number of consecutive values: 13; Time consuming: 86082ms, total : 100979ms83 consecutive times n=17051709, number of consecutive values: 13; time consuming: 86082ms, total: 100979ms84 consecutive times n=17051709, number of consecutive values: 13; time consuming: 86082ms, total: 100979ms85 times consecutive n=17051709, consecutive Number of values: 13; Time consuming: 86083ms, total: 100980ms 86 consecutive times n=17051709, number of consecutive values: 13; Time consuming: 86083ms, total: 100980ms 87 times consecutive n=17051709, number of consecutive values: 13; Time consuming: 86083ms, total : 100980ms88 consecutive times n=17051709, number of consecutive values: 13; time consumption: 86083ms, total: 100980ms89 times consecutive n=17051709, number of consecutive values: 13; time consumption: 86083ms, total number: 100980ms90 times consecutive n=20831325, consecutive Number of values: 15; Time consuming: 34772ms, total: 135752ms91 times consecutive n=20831325, number of consecutive values: 15; Time consuming: 34772ms, total: 135752ms92 times consecutive n=20831325, number of consecutive values: 15; Time consuming: 34772ms, total : 135752ms93 consecutive times n=20831325, number of consecutive values: 15; time consumption: 34772ms, total: 135752ms94 consecutive times n=20831325, number of consecutive values: 15; time consumption: 34772ms, total number: 135752ms95 times consecutive n=20831325, consecutive Number of values: 15; Time consuming: 34772ms, total: 135752ms96 times consecutive n=20831325, number of consecutive values: 15; Time consuming: 34772ms, total: 135752ms97 times consecutive n=20831325, number of consecutive values: 15; Time consuming: 34772ms, total : 135752ms98 consecutive times n=20831325, number of consecutive values: 15; time consumption: 34772ms, total: 135752ms99 times consecutive n=20831325, number of consecutive values: 15; time consumption: 34773ms, total number: 135753ms100 times consecutive n=20831325, consecutive Number of values: 15; Time consuming: 34773ms, total: 135753ms101 consecutive times n=20831325, number of consecutive values: 15; Time consuming: 34773ms, total: 135753ms102 times consecutive n=20831325, number of consecutive values: 15; Time consuming: 34773ms, total : 135753ms103 consecutive times n=20831325, number of consecutive values: 15; time consumption: 34773ms, total: 135753ms104 consecutive times n=20831325, number of consecutive values: 15; time consumption: 34773ms, total: 135753ms105 consecutive times n=47326695, number of consecutive values: 5; time consumption: 319130ms, total: 452155ms106 times consecutive n=47326695, number of consecutive values: 5; time consumption: 319131ms, total: 452156ms107 consecutive times n=47326695, number of consecutive values: 5; time consuming: 319131ms, total: 452156ms108 consecutive times n=47326695, number of consecutive values: 5; time consuming: 319131ms, total: 452156ms109 consecutive times n=47326695, number of consecutive values: 5; time consuming: 319131ms, total: 452156ms110 times consecutive n=122164749, number of consecutive values: 1; time consuming: 1395200ms, total: 1847356ms111 consecutive times n=189695661, number of consecutive values: 6; time consuming: 1705936ms, total: 3553292ms112 times consecutive n=189695661, number of consecutive values: 6; time consuming: 1705936ms, total: 3553292ms113 consecutive times n=189695661, number of consecutive values: 6; time consuming: 1705936ms, total: 3553292ms114 times consecutive n=189695661, number of consecutive values: 6; time consuming: 1705936ms, total: 3553292ms115 consecutive times n=189695661, number of consecutive values: 6; time consuming: 1705936ms, total: 3553292ms116 times consecutive n=189695661, number of consecutive values: 6; time consuming: 1705936ms, total: 3553292ms117 consecutive times n=191912785, number of consecutive values: 7; time consuming: 61964ms, total: 3615256ms118 times consecutive n=191912785, number of consecutive values: 7; time consuming: 61964ms, total: 3615256ms119 consecutive times n=191912785, number of consecutive values: 7; time consumption: 61964ms, total: 3615256ms120 times consecutive n=191912785, number of consecutive values: 7; time consumption: 61964ms, total: 3615256ms121 consecutive times n=191912785, number of consecutive values: 7; time consuming: 61964ms, total: 3615256ms122 consecutive times n=191912785, number of consecutive values: 7; time consuming: 61964ms, total: 3615256ms123 consecutive times n=191912785, number of consecutive values: 7; time consumption: 61964ms, total: 3615256ms124 times consecutive n=387096135, number of consecutive values: 1; time consumption: 6650201ms, total number: 10265457ms----- This run has been completed, and the next value has exceeded 1000 times; useless time: 0ms, total: xxxxxx135395ms
. . . . . . The subsequent results have not yet been calculated.
The code looks like this:
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 ;/** * Six consecutive odd numbers a, a+2, a+4, a+6, a+8, a+10 are all composite numbers, find the smallest a */public class ZhishuTest { /** * Determine whether a number is a composite number. Compared with prime numbers* @param num * @return */ public static boolean He(int num){ // Square root 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; } /** * Main function* @param args */ public static void main(String[] args) { test(); } public static void test() { // Start time long startMillis = System.currentTimeMillis(); // Last completion time long preMillis = System.currentTimeMillis(); // This time completion time long curMillis = System.currentTimeMillis(); // int lianxu = 1000; int start = 1; int times = 1; for (int x = 1; x <= lianxu; x++) { if(times > x){ continue; // jump passed, enter the next loop} else { times = x; } List<Map<Integer, Integer>> resList = testTimesHe(x, start, false); // // If there is a number, process it if(null == resList || resList.isEmpty()){ // If it cannot be found, there will be no next one... // Deep nesting is too disgusting. . . break; } int size = resList.size(); // Traverse 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 traversal is so disgusting. Bad Java Set<Integer> keys= map.keySet(); Iterator<Integer> iteratorK = keys.iterator(); if(iteratorK.hasNext()){ Integer key = iteratorK.next( ); // Number of times Integer value = map.get(key); // Minimum n // // This completion time curMillis = System.currentTimeMillis(); // long allTimeout = curMillis - startMillis; long curTimeout = curMillis - preMillis; System.out.println(""+key+" consecutive times n="+value +", number of consecutive values: "+size + "; time consuming: " + curTimeout + " ms, total: "+allTimeout+"ms"); // Process data, those that have been processed greedily will not be processed if(key > 0 && value > 0){ times = key+1; start = value; } } } } // Include the last completion time preMillis = System.currentTimeMillis(); } // // This completion time curMillis = System.currentTimeMillis(); // long allTimeout = curMillis - startMillis; long curTimeout = curMillis - preMillis; System.out.println("This run has been completed, the next value has exceeded 100 times" + "; Useless time: " + curTimeout + "ms, total: "+allTimeout+"ms"); } /** * * Test times + 2 are the minimum n of composite numbers * @param times calculation times * @param start starting number * @param onlyStart only calculates a single start value. Used for recursion. External calls should be passed in * @return */ public static List<Map<Integer, Integer>> testTimesHe(int times,int start, boolean onlyStart) { // List<Map<Integer, Integer>> resList= new ArrayList<Map<Integer, Integer>>(); // // Defensive programming if(start < 1){ return resList; } if(0 == start % 2 ){ // Do not handle even numbers return resList; } if(times < 1){ times = 1; } // int result = -1; // for (int i = start; i < Integer.MAX_VALUE; i+=2) { // // Avoid continuous calculation without returning if(onlyStart && i > start){ // If start is not satisfied, just return directly resList; } for (int j = 0; j < times; j++) { int n = i + 2*j; // if(!He(n)){ break; // Inner exit} // if(j+1 == times){ // Run to the result. times It satisfies result = i; break;// It doesn’t matter whether you retreat or not, we run to the end of for} } // if(result > 0){ // //System.out.println("result = "+result ); // Map<Integer, Integer> resMap = new HashMap<Integer, Integer>(); resMap.put(times, result); resList.add(resMap); // Try the next number of times, recursion; In fact, this recursion can be further optimized; greedy algorithm, just add the next time. . . // startTimes, add this parameter directly. . . Greedy recursion? // One more time, starting from the number result int t = times +1; int s = result; List<Map<Integer, Integer>> nextList = testTimesHe(t, s, true); // If there is The numbers of the next level are added to the current result if(null != nextList && false==nextList.isEmpty()){ resList.addAll(nextList); } // break; // Outer layer exit } } // return resList; }}Note: There is still room for improvement, welcome to make corrections next time