前言
相关的知识点帖子《算法零基础100讲》(第7讲) 素数判定
今天是一个只有两题但是突然史诗级难度的题。大家不要灰心，我尽量用简单的语言来跟大家聊聊怎么写并且怎么去优化。
看了这篇文章能让每个人都100%通过这类题，但是建议大家不到万不得已不要用这类取巧的方式。
主要知识点
复杂度的素数判定方法
int isPrime(int n) { // (1) int i, sqrtn = sqrt(n + 1e-6); if(n <= 1) { return 0; // (2) } for(i = 2; i <= sqrtn; ++i) { if(n % i == 0) { // (3) return 0; } } return 1; // (4) }
其中n要加1e-6是因为，计算机内部存储数字是用的二进制，二进制无法精确表示十进制的小数会有误差，加上这个进行误差的消除。其实这个等式暗藏了浮点转整形的转换，你有看到么？
课后习题详解
回文素数
866. 回文素数
https://leetcode-cn.com/problems/prime-palindrome/
求出大于或等于 N 的最小回文素数。
思路1
利用一个函数来判断是否是回文。然后再判断是否是素数返回结果就好了。
顺序不能反，因为回文数判断快很多 只要O(1)而素数需要1/2指数量级。
bool huiwen(int n){ int s[10],i; for(i = 0;n;++i){ s[i] = n%10; n = n / 10; } for(int j = 0;j < i / 2;++j) if(s[j] != s[i - 1 -j]) return false; return true; } int primePalindrome(int n){ if(n == 1) return 2; int ans; for(int i = n; ; i++){ int sqrti = sqrt(i + 1e-6); bool flag = true; //printf("%d",sqrti); for(int j = 2;j <= sqrti; ++j) if(i % j == 0){ //printf("123"); flag = false; break; } if(flag && huiwen(i)){ ans = i; break; } } return ans; }
结果分析1
超时！惊不惊喜，意不意外，然后去看了一下官方的题解，给出的解释是8位的数字没有素数。
我就emmmmm？ 我哪知道去？这也太扯了吧，于是优化思路形成第二种。
思路2
我只要根据当前数字，找到大于他的最小回文数字，然后判断是否是素数，然后迭代就能找到满足题目的解了对不对。
所以有两个步骤
1.找对应的下一个回文数
其实比较简单，我就拿到前面的一半对称到后面就可以生成了，但是这样不能保证比我给的数字大，所以做个判断，如果不大我就把前面的数字加一就好了。但是我要有一个根据前面的一般数字生成后面数字的规则。👇k是代表是奇数位还是偶数位的
int huiwen(int n,int k){ int s[10],ans = n,wei = 0; while(n){ s[wei++] = n %10; n /= 10; } for(int i = k?1:0; i < wei; i++){ ans *= 10; ans += s[i]; } return ans; }
然后就是返回回文数字的函数，要注意的是如果给的值是边界也就是几个9的话需要进行+1再寻找。
int nexthuiwen(int n){ if(n % 10 == 9) n++;//边界条件 int s[10],ans,wei = 0,temp =n; while(n){ //判断位数 s[wei++] = n % 10; n /= 10; } if(wei % 2 == 1){ int wei1 = (wei - 1) / 2; for(int i = temp /pow(10,wei1);;i++){//截取前一半 ans = huiwen(i,1); if(ans > temp) break; } } else{ int wei2 = wei / 2; for(int i = temp/pow(10,wei2);;i++){//截取前一半 ans = huiwen(i,0); if(ans > temp) break; } } return ans; //返回回文数字 }
完整代码
其实很简单的，就是根据数字找下一个回文数，然后判断回文数是不是素数，如果是就返回。
int huiwen(int n,int k){ int s[10],ans = n,wei = 0; while(n){ s[wei++] = n %10; n /= 10; } for(int i = k?1:0; i < wei; i++){ ans *= 10; ans += s[i]; } return ans; } int nexthuiwen(int n){ if(n % 10 == 9) n++; int s[10],ans,wei = 0,temp =n; while(n){ s[wei++] = n % 10; n /= 10; } if(wei % 2 == 1){ int wei1 = (wei - 1) / 2; for(int i = temp /pow(10,wei1);;i++){ ans = huiwen(i,1); if(ans > temp) break; } } else{ int wei2 = wei / 2; for(int i = temp/pow(10,wei2);;i++){ ans = huiwen(i,0); if(ans > temp) break; } } return ans; } int primePalindrome(int n){ if(n == 1) return 2; int ans = 0; for(int i = n - 1; ; ){ i = nexthuiwen(i); //素数判定 int sqrti = sqrt(i + 1e-6); bool flag = true; for(int j = 2;j <= sqrti; ++j)// if(i % j == 0){ //printf("123"); flag = false; break; } if(flag){ ans = i; break; } } return ans; }
结果分析
完美！
丑数
剑指 Offer 49. 丑数
https://leetcode-cn.com/problems/chou-shu-lcof/
思路1
因为每个丑数都是通过一些2一些3一些5生成的，那么，如果我想要生成下一个丑数肯定是是在之前的所有丑数分别乘2乘3乘5得到的比上一个丑数大的数中最小的。(多绕绕 肯定能绕过来)
对应算法就是我有三个记录位置的指针，这三个指针分别指向x2、x3、x5后刚好比我之前生成的丑数大的元素，然后下一个元素就会在这三个数中产生。
for(int i = 1; i < n; i++){ int temp = min(*p2 * 2,*p3 * 3,*p5 * 5); num[i] = temp; while(*p2 * 2 <= temp) p2++; while(*p3 * 3 <= temp) p3++; while(*p5 * 5 <= temp) p5++; }
完整代码1
c好像没有取三个元素最小的，就随手写了个。不复杂。
int min(int a,int b, int c){ if(a > b) if(b > c) return c; else return b; else if(b < c) return a; else if(a > c) return c; else return a; } int nthUglyNumber(int n){ int num[1690] = {1}; int *p2 = num, *p3= num, *p5 = num; for(int i = 1; i < n; i++){ int temp = min(*p2 * 2,*p3 * 3,*p5 * 5); printf("%d\n",temp); printf("%d %d %d\n",*p2 * 2,*p3 * 3,*p5 * 5); num[i] = temp; while(*p2 * 2 <= temp) p2++; while(*p3 * 3 <= temp) p3++; while(*p5 * 5 <= temp) p5++; printf("%d %d %d\n",*p2,*p3,*p5); } return num[n - 1]; }
结果分析1
这种情况这么低的排名。。我怀疑他们作弊，所以
我们也作弊把！
耍赖方法
思路
其实很简答， 就1960个数字，保存到数组里查多快啊。
你如果问你怎么知道这1960个数字。让计算机算啊。你就是写出来指数的函数用你电脑算出来，你都能赢0.0
#include<cstdio> int min(int a,int b, int c){ if(a > b) if(b > c) return c; else return b; else if(b < c) return a; else if(a > c) return c; else return a; } int nthUglyNumber(int n){ int num[1690] = {1}; int *p2 = num, *p3= num, *p5 = num; for(int i = 1; i < n; i++){ int temp = min(*p2 * 2,*p3 * 3,*p5 * 5); printf("%d,",temp); //printf("%d %d %d\n",*p2 * 2,*p3 * 3,*p5 * 5); num[i] = temp; while(*p2 * 2 <= temp) p2++; while(*p3 * 3 <= temp) p3++; while(*p5 * 5 <= temp) p5++; //printf("%d %d %d\n",*p2,*p3,*p5); } return num[n - 1]; } int main(){ freopen("output.txt","w",stdout); nthUglyNumber(1690); return 0; } int nthUglyNumber(int n){ int num[] ={0,1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40,45,48,50,54,60,64,72,75,80,81,90,96,100,108,120,125,128,135,144,150,160,162,180,192,200,216,225,240,243,250,256,270,288,300,320,324,360,375,384,400,405,432,450,480,486,500,512,540,576,600,625,640,648,675,720,729,750,768,800,810,864,900,960,972,1000,1024,1080,1125,1152,1200,1215,1250,1280,1296,1350,1440,1458,1500,1536,1600,1620,1728,1800,1875,1920,1944,2000,2025,2048,2160,2187,2250,2304,2400,2430,2500,2560,2592,2700,2880,2916,3000,3072,3125,3200,3240,3375,3456,3600,3645,3750,3840,3888,4000,4050,4096,4320,4374,4500,4608,4800,4860,5000,5120,5184,5400,5625,5760,5832,6000,6075,6144,6250,6400,6480,6561,6750,6912,7200,7290,7500,7680,7776,8000,8100,8192,8640,8748,9000,9216,9375,9600,9720,10000,10125,10240,10368,10800,10935,11250,11520,11664,12000,12150,12288,12500,12800,12960,13122,13500,13824,14400,14580,15000,15360,15552,15625,16000,16200,16384,16875,17280,17496,18000,18225,18432,18750,19200,19440,19683,20000,20250,20480,20736,21600,21870,22500,23040,23328,24000,24300,24576,25000,25600,25920,26244,27000,27648,28125,28800,29160,30000,30375,30720,31104,31250,32000,32400,32768,32805,33750,34560,34992,36000,36450,36864,37500,38400,38880,39366,40000,40500,40960,41472,43200,43740,45000,46080,46656,46875,48000,48600,49152,50000,50625,51200,51840,52488,54000,54675,55296,56250,57600,58320,59049,60000,60750,61440,62208,62500,64000,64800,65536,65610,67500,69120,69984,72000,72900,73728,75000,76800,77760,78125,78732,80000,81000,81920,82944,84375,86400,87480,90000,91125,92160,93312,93750,96000,97200,98304,98415,100000,101250,102400,103680,104976,108000,109350,110592,112500,115200,116640,118098,120000,121500,122880,124416,125000,128000,129600,131072,131220,135000,138240,139968,140625,144000,145800,147456,150000,151875,153600,155520,156250,157464,160000,162000,163840,164025,165888,168750,172800,174960,177147,180000,182250,184320,186624,187500,192000,194400,196608,196830,200000,202500,204800,207360,209952,216000,218700,221184,225000,230400,233280,234375,236196,240000,243000,245760,248832,250000,253125,256000,259200,262144,262440,270000,273375,276480,279936,281250,288000,291600,294912,295245,300000,303750,307200,311040,312500,314928,320000,324000,327680,328050,331776,337500,345600,349920,354294,360000,364500,368640,373248,375000,384000,388800,390625,393216,393660,400000,405000,409600,414720,419904,421875,432000,437400,442368,450000,455625,460800,466560,468750,472392,480000,486000,491520,492075,497664,500000,506250,512000,518400,524288,524880,531441,540000,546750,552960,559872,562500,576000,583200,589824,590490,600000,607500,614400,622080,625000,629856,640000,648000,655360,656100,663552,675000,691200,699840,703125,708588,720000,729000,737280,746496,750000,759375,768000,777600,781250,786432,787320,800000,810000,819200,820125,829440,839808,843750,864000,874800,884736,885735,900000,911250,921600,933120,937500,944784,960000,972000,983040,984150,995328,1000000,1012500,1024000,1036800,1048576,1049760,1062882,1080000,1093500,1105920,1119744,1125000,1152000,1166400,1171875,1179648,1180980,1200000,1215000,1228800,1244160,1250000,1259712,1265625,1280000,1296000,1310720,1312200,1327104,1350000,1366875,1382400,1399680,1406250,1417176,1440000,1458000,1474560,1476225,1492992,1500000,1518750,1536000,1555200,1562500,1572864,1574640,1594323,1600000,1620000,1638400,1640250,1658880,1679616,1687500,1728000,1749600,1769472,1771470,1800000,1822500,1843200,1866240,1875000,1889568,1920000,1944000,1953125,1966080,1968300,1990656,2000000,2025000,2048000,2073600,2097152,2099520,2109375,2125764,2160000,2187000,2211840,2239488,2250000,2278125,2304000,2332800,2343750,2359296,2361960,2400000,2430000,2457600,2460375,2488320,2500000,2519424,2531250,2560000,2592000,2621440,2624400,2654208,2657205,2700000,2733750,2764800,2799360,2812500,2834352,2880000,2916000,2949120,2952450,2985984,3000000,3037500,3072000,3110400,3125000,3145728,3149280,3188646,3200000,3240000,3276800,3280500,3317760,3359232,3375000,3456000,3499200,3515625,3538944,3542940,3600000,3645000,3686400,3732480,3750000,3779136,3796875,3840000,3888000,3906250,3932160,3936600,3981312,4000000,4050000,4096000,4100625,4147200,4194304,4199040,4218750,4251528,4320000,4374000,4423680,4428675,4478976,4500000,4556250,4608000,4665600,4687500,4718592,4723920,4782969,4800000,4860000,4915200,4920750,4976640,5000000,5038848,5062500,5120000,5184000,5242880,5248800,5308416,5314410,5400000,5467500,5529600,5598720,5625000,5668704,5760000,5832000,5859375,5898240,5904900,5971968,6000000,6075000,6144000,6220800,6250000,6291456,6298560,6328125,6377292,6400000,6480000,6553600,6561000,6635520,6718464,6750000,6834375,6912000,6998400,7031250,7077888,7085880,7200000,7290000,7372800,7381125,7464960,7500000,7558272,7593750,7680000,7776000,7812500,7864320,7873200,7962624,7971615,8000000,8100000,8192000,8201250,8294400,8388608,8398080,8437500,8503056,8640000,8748000,8847360,8857350,8957952,9000000,9112500,9216000,9331200,9375000,9437184,9447840,9565938,9600000,9720000,9765625,9830400,9841500,9953280,10000000,10077696,10125000,10240000,10368000,10485760,10497600,10546875,10616832,10628820,10800000,10935000,11059200,11197440,11250000,11337408,11390625,11520000,11664000,11718750,11796480,11809800,11943936,12000000,12150000,12288000,12301875,12441600,12500000,12582912,12597120,12656250,12754584,12800000,12960000,13107200,13122000,13271040,13286025,13436928,13500000,13668750,13824000,13996800,14062500,14155776,14171760,14348907,14400000,14580000,14745600,14762250,14929920,15000000,15116544,15187500,15360000,15552000,15625000,15728640,15746400,15925248,15943230,16000000,16200000,16384000,16402500,16588800,16777216,16796160,16875000,17006112,17280000,17496000,17578125,17694720,17714700,17915904,18000000,18225000,18432000,18662400,18750000,18874368,18895680,18984375,19131876,19200000,19440000,19531250,19660800,19683000,19906560,20000000,20155392,20250000,20480000,20503125,20736000,20971520,20995200,21093750,21233664,21257640,21600000,21870000,22118400,22143375,22394880,22500000,22674816,22781250,23040000,23328000,23437500,23592960,23619600,23887872,23914845,24000000,24300000,24576000,24603750,24883200,25000000,25165824,25194240,25312500,25509168,25600000,25920000,26214400,26244000,26542080,26572050,26873856,27000000,27337500,27648000,27993600,28125000,28311552,28343520,28697814,28800000,29160000,29296875,29491200,29524500,29859840,30000000,30233088,30375000,30720000,31104000,31250000,31457280,31492800,31640625,31850496,31886460,32000000,32400000,32768000,32805000,33177600,33554432,33592320,33750000,34012224,34171875,34560000,34992000,35156250,35389440,35429400,35831808,36000000,36450000,36864000,36905625,37324800,37500000,37748736,37791360,37968750,38263752,38400000,38880000,39062500,39321600,39366000,39813120,39858075,40000000,40310784,40500000,40960000,41006250,41472000,41943040,41990400,42187500,42467328,42515280,43046721,43200000,43740000,44236800,44286750,44789760,45000000,45349632,45562500,46080000,46656000,46875000,47185920,47239200,47775744,47829690,48000000,48600000,48828125,49152000,49207500,49766400,50000000,50331648,50388480,50625000,51018336,51200000,51840000,52428800,52488000,52734375,53084160,53144100,53747712,54000000,54675000,55296000,55987200,56250000,56623104,56687040,56953125,57395628,57600000,58320000,58593750,58982400,59049000,59719680,60000000,60466176,60750000,61440000,61509375,62208000,62500000,62914560,62985600,63281250,63700992,63772920,64000000,64800000,65536000,65610000,66355200,66430125,67108864,67184640,67500000,68024448,68343750,69120000,69984000,70312500,70778880,70858800,71663616,71744535,72000000,72900000,73728000,73811250,74649600,75000000,75497472,75582720,75937500,76527504,76800000,77760000,78125000,78643200,78732000,79626240,79716150,80000000,80621568,81000000,81920000,82012500,82944000,83886080,83980800,84375000,84934656,85030560,86093442,86400000,87480000,87890625,88473600,88573500,89579520,90000000,90699264,91125000,92160000,93312000,93750000,94371840,94478400,94921875,95551488,95659380,96000000,97200000,97656250,98304000,98415000,99532800,100000000,100663296,100776960,101250000,102036672,102400000,102515625,103680000,104857600,104976000,105468750,106168320,106288200,107495424,108000000,109350000,110592000,110716875,111974400,112500000,113246208,113374080,113906250,114791256,115200000,116640000,117187500,117964800,118098000,119439360,119574225,120000000,120932352,121500000,122880000,123018750,124416000,125000000,125829120,125971200,126562500,127401984,127545840,128000000,129140163,129600000,131072000,131220000,132710400,132860250,134217728,134369280,135000000,136048896,136687500,138240000,139968000,140625000,141557760,141717600,143327232,143489070,144000000,145800000,146484375,147456000,147622500,149299200,150000000,150994944,151165440,151875000,153055008,153600000,155520000,156250000,157286400,157464000,158203125,159252480,159432300,160000000,161243136,162000000,163840000,164025000,165888000,167772160,167961600,168750000,169869312,170061120,170859375,172186884,172800000,174960000,175781250,176947200,177147000,179159040,180000000,181398528,182250000,184320000,184528125,186624000,187500000,188743680,188956800,189843750,191102976,191318760,192000000,194400000,195312500,196608000,196830000,199065600,199290375,200000000,201326592,201553920,202500000,204073344,204800000,205031250,207360000,209715200,209952000,210937500,212336640,212576400,214990848,215233605,216000000,218700000,221184000,221433750,223948800,225000000,226492416,226748160,227812500,229582512,230400000,233280000,234375000,235929600,236196000,238878720,239148450,240000000,241864704,243000000,244140625,245760000,246037500,248832000,250000000,251658240,251942400,253125000,254803968,255091680,256000000,258280326,259200000,262144000,262440000,263671875,265420800,265720500,268435456,268738560,270000000,272097792,273375000,276480000,279936000,281250000,283115520,283435200,284765625,286654464,286978140,288000000,291600000,292968750,294912000,295245000,298598400,300000000,301989888,302330880,303750000,306110016,307200000,307546875,311040000,312500000,314572800,314928000,316406250,318504960,318864600,320000000,322486272,324000000,327680000,328050000,331776000,332150625,335544320,335923200,337500000,339738624,340122240,341718750,344373768,345600000,349920000,351562500,353894400,354294000,358318080,358722675,360000000,362797056,364500000,368640000,369056250,373248000,375000000,377487360,377913600,379687500,382205952,382637520,384000000,387420489,388800000,390625000,393216000,393660000,398131200,398580750,400000000,402653184,403107840,405000000,408146688,409600000,410062500,414720000,419430400,419904000,421875000,424673280,425152800,429981696,430467210,432000000,437400000,439453125,442368000,442867500,447897600,450000000,452984832,453496320,455625000,459165024,460800000,466560000,468750000,471859200,472392000,474609375,477757440,478296900,480000000,483729408,486000000,488281250,491520000,492075000,497664000,500000000,503316480,503884800,506250000,509607936,510183360,512000000,512578125,516560652,518400000,524288000,524880000,527343750,530841600,531441000,536870912,537477120,540000000,544195584,546750000,552960000,553584375,559872000,562500000,566231040,566870400,569531250,573308928,573956280,576000000,583200000,585937500,589824000,590490000,597196800,597871125,600000000,603979776,604661760,607500000,612220032,614400000,615093750,622080000,625000000,629145600,629856000,632812500,637009920,637729200,640000000,644972544,645700815,648000000,655360000,656100000,663552000,664301250,671088640,671846400,675000000,679477248,680244480,683437500,688747536,691200000,699840000,703125000,707788800,708588000,716636160,717445350,720000000,725594112,729000000,732421875,737280000,738112500,746496000,750000000,754974720,755827200,759375000,764411904,765275040,768000000,774840978,777600000,781250000,786432000,787320000,791015625,796262400,797161500,800000000,805306368,806215680,810000000,816293376,819200000,820125000,829440000,838860800,839808000,843750000,849346560,850305600,854296875,859963392,860934420,864000000,874800000,878906250,884736000,885735000,895795200,900000000,905969664,906992640,911250000,918330048,921600000,922640625,933120000,937500000,943718400,944784000,949218750,955514880,956593800,960000000,967458816,972000000,976562500,983040000,984150000,995328000,996451875,1000000000,1006632960,1007769600,1012500000,1019215872,1020366720,1024000000,1025156250,1033121304,1036800000,1048576000,1049760000,1054687500,1061683200,1062882000,1073741824,1074954240,1076168025,1080000000,1088391168,1093500000,1105920000,1107168750,1119744000,1125000000,1132462080,1133740800,1139062500,1146617856,1147912560,1152000000,1162261467,1166400000,1171875000,1179648000,1180980000,1194393600,1195742250,1200000000,1207959552,1209323520,1215000000,1220703125,1224440064,1228800000,1230187500,1244160000,1250000000,1258291200,1259712000,1265625000,1274019840,1275458400,1280000000,1289945088,1291401630,1296000000,1310720000,1312200000,1318359375,1327104000,1328602500,1342177280,1343692800,1350000000,1358954496,1360488960,1366875000,1377495072,1382400000,1399680000,1406250000,1415577600,1417176000,1423828125,1433272320,1434890700,1440000000,1451188224,1458000000,1464843750,1474560000,1476225000,1492992000,1500000000,1509949440,1511654400,1518750000,1528823808,1530550080,1536000000,1537734375,1549681956,1555200000,1562500000,1572864000,1574640000,1582031250,1592524800,1594323000,1600000000,1610612736,1612431360,1620000000,1632586752,1638400000,1640250000,1658880000,1660753125,1677721600,1679616000,1687500000,1698693120,1700611200,1708593750,1719926784,1721868840,1728000000,1749600000,1757812500,1769472000,1771470000,1791590400,1793613375,1800000000,1811939328,1813985280,1822500000,1836660096,1843200000,1845281250,1866240000,1875000000,1887436800,1889568000,1898437500,1911029760,1913187600,1920000000,1934917632,1937102445,1944000000,1953125000,1966080000,1968300000,1990656000,1992903750,2000000000,2013265920,2015539200,2025000000,2038431744,2040733440,2048000000,2050312500,2066242608,2073600000,2097152000,2099520000,2109375000,2123366400}; return num[n]; }
下面的数组就是上面的函数生成的。直接查表就好了。
结果分析
有什么好说的。。
今日总结
打表查表是一种万不得一的方式，也确实是一种空间换时间的方法，但是不太推荐，有兴趣的同学可以试试能不能打一下第一题的表然后也O(1)解决。
下课。明日继续，乾坤未定。你我皆黑马！
