首页 团队成员,上杉九月的文章

文章简介

作者:上杉九月

排版与发布:上杉九月

前言

记录一下洛谷的做题详细思路,方便自己,也方便其他想要做题的同学。

为了方便访问,所有内容将在此文章更新,我会做好分类。

欢迎收藏!

如果你有对于这些题目不同的算法,欢迎在评论区与我交流。

正文

循环结构

[P1217 [USACO1.5]回文质数 Prime Palindromes](https://www.luogu.com.cn/problem/P1217)

题目描述

因为 151 既是一个质数又是一个回文数(从左到右和从右到左是看一样的),所以 151 是回文质数。

写一个程序来找出范围 $[a,b] (5 \le a < b \le 100,000,000)$( 一亿)间的所有回文质数。

输入输出格式

输入格式

第 1 行: 二个整数 a 和 b .

输出格式

输出一个回文质数的列表,一行一个。

输入输出样例

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

说明/提示

Hint 1: Generate the palindromes and see if they are prime.

提示 1: 找出所有的回文数再判断它们是不是质数(素数)

Hint 2: Generate palindromes by combining digits properly. You might need more than one of the loops like below.

提示 2: 要产生正确的回文数,你可能需要几个像下面这样的循环。

题目翻译来自NOCOW。

产生长度为5的回文数:

for (d1 = 1; d1 <= 9; d1+=2) {    // 只有奇数才会是素数
     for (d2 = 0; d2 <= 9; d2++) {
         for (d3 = 0; d3 <= 9; d3++) {
           palindrome = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;//(处理回文数...)
         }
     }
 }

题解

代码:上杉九月

线性筛素数算法:洛谷@学委

原理性证明:学委的博客

回文数判断

从个位开始,倒序输出,最后与原数判断

质数判断

这里用到线性筛

关于质数请看

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXN 100000000
using namespace std;
bool Prime_Map[100000001];//创建质数地图
int Prime[1000000];//int数组存质数
int cnt;//定义一个标记,记录质数的存储下标
bool Judge_Hw(int n)//回文数判断
{
    int m = 0;
    int x = n;//n为输入数据,x为中介数据
    while(x!=0)
    {
        m = m * 10 + x % 10;
        x /= 10;
    }
    if( m == n)
    {
        return true;
    }
    else
    {
        return false;
    }
}
void Judge_Prime(int n)
{
    memset(Prime_Map, 1, sizeof(Prime_Map));//初始化
    Prime_Map[1] = 0;
    for(int i = 2; i <= n; i++)
    {
        if(Prime_Map[i])
        {
            Prime[++cnt] = i;//如果下标i没有被筛选掉,存入质数数组
        }

        for(int j = 1; j <= cnt && i * Prime[j] <= n; j++ )
        {
            //对质数倍数进行筛出
            Prime_Map[i * Prime[j]] = 0;

            if(i % Prime[j] == 0)
            {
                break;
            }
        }
    }
}
int main()
{
    int a, b;
    cin>>a>>b;
    if(b >= 10000000)//没有超过1千万的质数回文数,洛谷最后一个点会卡RE
    {
        b = 10000000;
    }
    Judge_Prime(b);
    for(int i = 1; i <= cnt; i++)
    {
        if(Judge_Hw(Prime[i]) == 1 && Prime[i] >= a)
        {
            printf("%d\n", Prime[i]);
        }
    }
    system("pause");
    return 0;
}

about_me




文章评论

目录