【洛谷入门3】循环结构 P1217 回文质数 Prime Palindromes

你的名字 2022-10-26 04:00 188阅读 0赞

## P1217 \[USACO1.5\]回文质数 Prime Palindromes ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center]

输入 
    5 500
    输出 
    5
    7
    11
    101
    131
    151
    181
    191
    313
    353
    373
    383

1、判断回文

bool hw(int x)
    {
        
    	int s=0,y=x;
    	while(y!=0)
    	{
        
    		s=s*10+y%10;
    		y=y/10;
    	}
    	if(s==x) return 1;
    	else return 0;
    }

2、判断素数

bool prime(int x)
    {
        
    	if(x==1) return 0;
    	for(int i=2;i<=sqrt(x);i++)
    	{
        
    		if(x%i==0) return 0;
    	}
    	return 1;
    }

3、完整代码

#include<bits/stdc++.h>
    using namespace std;
    bool hw(int x)
    {
        
    	int s=0,y=x;
    	while(y!=0)
    	{
        
    		s=s*10+y%10;
    		y=y/10;
    	}
    	if(s==x) return 1;
    	else return 0;
    } 
    bool prime(int x)
    {
        
    	if(x==1) return 0;
    	for(int i=2;i<=sqrt(x);i++)
    	{
        
    		if(x%i==0) return 0;
    	}
    	return 1;
    }
    int main()
    {
        
    	int a,b;
    	cin>>a>>b;
    	for(int i=a;i<=b;i++)
    	{
        
    		if(i==9989900) break;
    		if(hw(i)&&prime(i)) cout<<i<<endl;
    	}
    	return 0;
    }

如果不加`if(i==9989900) break;`这一步，最后一个测试点会一直TLE。然后看了题解，选择直接特判了，如果i是9989900直接退出。

**注意：** 先判断回文是因为回文比较少，减少判断时间（在c++中，if语句里面如果有&&符号，如果前面一个判断为假，那么程序不会再进行后面的判断）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center]: /images/20221024/a122b0ffe6ee4cf49604fdbfdf175e95.png