leetcode 866. 回文素数【构造】

蔚落 2023-01-19 09:46 21阅读 0赞

[题解][Link 1]

> 将N  
> 例如N= 12321  
> 从中间劈开，取左半边，如果长度不是偶数，就左边多取一个  
> 这里取 n= 1234  
> 然后拿着n依次递增，  
> 然后将n的另一半拼接在n的后面 如下

所以偶数和奇数长度都可能出现 所以我们都要进行计算一遍取最小值

#define debug(x) cout<<#x<<": "<<(x)<<endl;
    class Solution { 
    public:
        
        int N;
        bool isp(int n){ 
            if(n<2){ 
                return false;
            }
            int sq = sqrt(n);
            for(int i=2;i<=sq;++i){ 
                if(n%i==0){ 
                    return false;
                }
            }
            return true;
        }
        
        int getw(int a){ 
            int ret=1;
            a/=10;
            while(a>0){ 
                ret++;
                a/=10;
            }
            return ret;
        }
        
        int cal(bool ji,int st){ 
            
            int r=0;
            for(;r<=2*1e8;){ 
    
                int ste = st;
                r = 0;
                if(ji){ 
                    ste/=10; 
                }
    
                while(ste>0){ 
                    r *= 10;
                    r += ste%10;
                    ste/=10;
                }
                
                if(ji){ 
                    r = st*pow(10,getw(st)-1) + r;
                }else{ 
                   r = st*pow(10,getw(st)) + r;
                }
                if( isp(r) && r >= N){ 
                    return r;
                }
                st++;
            }
            return -1;
        }
        
        int primePalindrome(int N) { 
            
                            // 0 1 2 3 4 5 6 7 8 9 10
            vector<int> s10 = { 2,2,2,3,5,5,7,7,11,11,11};
            
            if(N<=10){ 
                return s10[N];
            }
            this->N = N;
            int n = getw(N);
            // 123 321 3
            // 1234321 4
            int st = N/pow(10,n/2);
            
            int r1 = cal(0,st);
            int r2 = cal(1,st);
            
            if(r1!=-1 && r2!=-1){ 
                return min(r1,r2);
            }else{ 
                return max(r1,r2);
            }
            return -1;
        }
    };

![在这里插入图片描述][20210509192442330.png]

[Link 1]: https://leetcode-cn.com/problems/prime-palindrome/solution/hui-wen-su-shu-by-leetcode/
[20210509192442330.png]: /images/20221021/aa4a0266eb1e449d8b37c541ae4662ad.png