pprime

"HTML Tidy for Linux (vers 25 March 2009), see www.w3.org">

</title></p> <style type="text/css"> div.c3 {font-size: 14px;}<br /> div.c2 {text-align: center}<br /> span.c1 {font-family: Verdana,Tahoma,sans-serif,Arial,Lucida Sans,Gill Sans}<br /> </style><br /> </head></p> <p><body></p> <div id="BlogArticleDetail" class="c3"> <pre> All tests OK. <br>Your program ('pprime') produced all correct answers! This is your submission #10 for this problem. <b>Congratulations!</b> <br><br>无论判断<span class="c1">所</span>有质数还是回文数都无法解决，必须按位广搜，分支限界。<br /> </pre></p> <div class="c2"> <h1>Prime Palindromes</h1><br /> </div></p> <p>The number 151 is a prime palindrome because it is both a<br /> prime number and a palindrome (it is the same number when read<br /> forward as backward). Write a program that finds all prime<br /> palindromes in the range of two supplied numbers a and b (5<br /> <= a < b <= 100,000,000); both a and b are considered<br /> to be within the range .</p><br /> <a id="more"></a><a id="more-21"></a></p> <h3>PROGRAM NAME: pprime</h3></p> <h3>INPUT FORMAT</h3></p> <table> <tbody> <tr> <td>Line 1:</td></p> <td>Two integers, a and b</td><br /> </tr><br /> </tbody><br /> </table></p> <h3>SAMPLE INPUT (file pprime.in)</h3></p> <pre> 5 500<br /> </pre></p> <h3>OUTPUT FORMAT</h3>The list of palindromic primes in<br /> numerical order, one per line.</p> <h3>SAMPLE OUTPUT (file pprime.out)</h3></p> <pre> 5 7 11 101 131 151 181 191 313 353 373 383<br>/*<br>ID: hippo he<br>LANG: C++<br>TASK: pprime<br>*/<br>#include<iostream><br>#include<stack><br>#include<vector><br>#include<fstream><br>#include <queue><br>#include<algorithm><br>using namespace std;<br>int A,B;<br>typedef pair<int,int> Node;<br>void input(){<br> ifstream in("pprime.in");<br> in>>A>>B;<br> in.close();<br>}<br>void output(vector<int>& res){<br> ofstream out("pprime.out");<br> for (int it = 0; it < res.size(); it++) {<br> out<<res[it]<<endl;<br> }<br> out.close();<br>}<br>bool isprime(int n)<br>{<br> if(n==2||n==3||n==5||n==7)return true;<br> else if(n==1||n%2==0)return false;<br> for(int i=3;i*i<=n;i+=2)<br> if(n%i==0)return false;<br> return true;<br>}<br>int reflect(Node a){<br> int n=a.first;<br> int depth=a.second;<br> stack<int> tmp1,tmp2;<br> while(depth--){<br> tmp1.push(n%10);<br> n/=10;<br> }<br> while(!tmp1.empty()){<br> tmp2.push(tmp1.top());<br> tmp1.pop();<br> }<br> tmp1=tmp2;<br><br> while(!tmp1.empty()){<br> tmp2.push(tmp1.top());<br> tmp1.pop();<br> }<br><br> int res=0;<br> res+=tmp2.top();<br> tmp2.pop();<br> while(!tmp2.empty()){<br> res*=10;<br> res+=tmp2.top();<br> tmp2.pop();<br> }<br> return res;<br>}<br>int reverse(Node a){<br> int n=a.first;<br> int depth=a.second;<br> stack<int> tmp1,tmp2;<br> while(depth--){<br> tmp1.push(n%10);<br> n/=10;<br> }<br> while(!tmp1.empty()){<br> tmp2.push(tmp1.top());<br> tmp1.pop();<br> }<br> tmp1=tmp2;<br><br> tmp2.pop();<br> while(!tmp1.empty()){<br> tmp2.push(tmp1.top());<br> tmp1.pop();<br> }<br><br> int res=0;<br> res+=tmp2.top();<br> tmp2.pop();<br> while(!tmp2.empty()){<br> res*=10;<br> res+=tmp2.top();<br> tmp2.pop();<br> }<br> return res;<br>}<br>void bfs(int init,vector<int>& res,int depth,int max,int min){<br> queue<Node> ints;<br> Node ini;<br> ini.first=init;<br> ini.second=1;<br> if(ini.second*2-1<=depth)<br> ints.push(ini);<br><br> int x=reflect(ini);<br> int y=reverse(ini);<br> if(x>=min&&x<=max&&isprime(x)&&ini.second*2<=depth)<br> res.push_back(x);<br> if(y>=min&&y<=max&&isprime(y)&&ini.second*2-1<=depth)<br> res.push_back(y);<br><br> while(!ints.empty()){<br> Node tmp=ints.front();<br> ints.pop();<br> for (int i = 0; i <= 9; i++) {<br> Node neb;<br> neb.first=tmp.first*10+i;<br> neb.second=tmp.second+1;<br><br> if(neb.first>max)return;<br> if(neb.second*2-1<=depth)<br> ints.push(neb);<br> else return;<br><br> int x=reflect(neb);<br> int y=reverse(neb);<br> if(x>=min&&x<=max&&isprime(x)&&ini.second*2<=depth)<br> res.push_back(x);<br> if(y>=min&&y<=max&&isprime(y)&&ini.second*2-1<=depth)<br> res.push_back(y);<br><br> }<br> }<br>}<br>void Bfs(vector<int> &res,int depth,int max,int min){<br> bfs(1,res,depth,max,min);<br> bfs(3,res,depth,max,min);<br> bfs(5,res,depth,max,min);<br> bfs(7,res,depth,max,min);<br> bfs(9,res,depth,max,min);<br>}<br>int main(int argc, const char *argv[])<br>{<br> vector<int> res;<br> int depth=0;<br> input();<br> int tmp=B;<br> while(tmp){<br> tmp/=10;<br> depth++;<br> }<br> Bfs(res,depth,B,A);<br><br> sort(res.begin(),res.end());<br> res.erase(unique(res.begin(),res.end()),res.end());<br> output(res);<br><br> return 0;<br>}<br> <br><br><br /> </pre><br /> </div><br /> </body><br /> </html></p> <footer class="entry-meta"> <span class="entry-tags"><a href="https://jaceho.github.io/tags/#prime" title="Pages tagged prime" class="tag"><span class="term">prime</span></a><a href="https://jaceho.github.io/tags/#usaco" title="Pages tagged usaco" class="tag"><span class="term">usaco</span></a><a href="https://jaceho.github.io/tags/#algorithms" title="Pages tagged algorithms" class="tag"><span class="term">algorithms</span></a></span> <div class="social-share"> <ul class="socialcount socialcount-small inline-list"> <li class="facebook"><a href="https://www.facebook.com/sharer/sharer.php?u=https://jaceho.github.io/pprime/" title="Share on Facebook"><span class="count"><i class="fa fa-facebook-square"></i> Like</span></a></li> <li class="twitter"><a href="https://twitter.com/intent/tweet?text=https://jaceho.github.io/pprime/" title="Share on Twitter"><span class="count"><i class="fa fa-twitter-square"></i> Tweet</span></a></li> <li class="googleplus"><a href="https://plus.google.com/share?url=https://jaceho.github.io/pprime/" title="Share on Google Plus"><span class="count"><i class="fa fa-google-plus-square"></i> +1</span></a></li> </ul> </div> </footer> </div> <div class="read-more"> <div class="read-more-header"> <a href="https://jaceho.github.io/sprime/" class="read-more-btn">Read More</a> </div> <div class="read-more-content"> <h3><a href="https://jaceho.github.io/machine-learning-regress/" title="分析预测模型在机器学习中的应用之线性回归">分析预测模型在机器学习中的应用之线性回归</a></h3> <p>回归能做任何事情 <a href="https://jaceho.github.io/machine-learning-regress/">Continue reading</a></p> </div> <div class="read-more-list"> <div class="list-item"> <h4><a href="https://jaceho.github.io/android-thread-process/" title="android中的线程与进程模型">android中的线程与进程模型</a></h4> <span>Published on June 15, 2016</span> </div> <div class="list-item"> <h4><a href="https://jaceho.github.io/android-image/" title="android内存优化之图片加载">android内存优化之图片加载</a></h4> <span>Published on June 11, 2016</span> </div> </div> </div> </article> </div> <div class="footer-wrapper"> <footer role="contentinfo"> <span>© 2026 何杰 · 北京</span> <span class="foot-links"> <a href="https://jaceho.github.io/posts/">写作</a> <a href="https://jaceho.github.io/me/">作品</a> <a href="https://jaceho.github.io/me/contact.html">合作</a> <a href="mailto:kimiscircle@gmail.com">邮箱</a> </span> </footer> </div> <script>window.jQuery || document.write('<script src="https://jaceho.github.io/assets/js/vendor/jquery-1.9.1.min.js"><\/script>')</script> <script src="https://jaceho.github.io/assets/js/scripts.min.js"></script> <script src="https://jaceho.github.io/assets/js/site.js" defer></script> </body> </html>