【洛谷】P1217 回文质数

#include<stdio.h>
#include<math.h>

int IsPrime(int n)  //判断素数
{
 if(n <= 1)
  return 0;
 if(n == 2)
  return 1;
 for(int i = 2;i <= (int)sqrt(n);i++)
  if(n%i==0)
   return 0;
 return 1; 
}

int IsPalindrome(int n)  //判断回文数
{
 int temp = n;
 int sum = 0;
 while (n != 0)
 {
  sum = sum * 10 + n % 10;
  n /= 10;
 }
 if (sum == temp)
  return 1;
 else
  return 0;
}

int main()
{
 int begin, end;
 scanf("%d%d",&begin,&end);
 
 //因为偶数除了2之外都不是素数，所以只需判断所有的奇数是否是素数，即从3开始每次+2
 if(begin%2==0)  
  begin += 1;
  
//没有这一句的，最后一个数据过不了，被题解里的大佬安排，发现一亿以内最大回文质数也就是9989899，然后这一行代码就诞生了。。。
 if(end>9999999)
  end = 9999999;
  
 for (int i = begin; i <= end; i += 2)
 {
  if (IsPalindrome(i)&&IsPrime(i))
    printf("%d\n",i);
 }
 return 0;
}

线性筛——欧拉筛法

c语言定义一维数组，元素未初始化，那数组元素默认值是什么
(1)全局变量
未初始化的全局变量是 0 
(2)局部变量
<1>Debug版
      是填充字符, 比如可能是 0xCDCDCDCD 等
<2>Release版
     是乱码, 也就是这个地方原来(在这之前被其他变量使用的时候)遗留下来的数据.

#include<iostream>
#include<cstdio>
#define MAXN 10000005
using namespace std;
int prime[MAXN];
bool pp[MAXN];
int vis[MAXN];

bool pd_h(int x)
{
    int y=x,num=0;//int y=x,防止x被改变
    while (y!=0)
    {
        num=num*10+y%10;//上一次数字的记录进位再加上下一位数
        y/=10;
    } 
    if (num==x) return 1;
    else return 0;
}

int main()
{
    int a,b;
    cin>>a>>b;
    int cnt=0;
    if(b>10000000) b=10000000;
    for(int i=2;i<=b;i++)
    {
        if(!vis[i]) prime[cnt++]=i,pp[i]=1;
        for(int j=0;j<cnt&&i*prime[j]<=b;j++)
        {
            vis[i*prime[j]]=i;
            if(i%prime[j]==0) break;
        }
    }
    for(int i=a;i<=b;i++)
    {
        if(i>10000000) break;
        if(pd_h(i)&&pp[i]) printf("%d\n",i);
    }
}

【洛谷】P1217 回文质数

相关推荐