PAT_A1152#Google Recruitment
Source:
Description:
In July 2004, Google posted on a giant billboard along Highway 101 in Silicon Valley (shown in the picture below) for recruitment. The content is super-simple, a URL consisting of the first 10-digit prime found in consecutive digits of the natural constant e. The person who could find this prime number could go to the next step in Google's hiring process by visiting this website.
The natural constant e is a well known transcendental number(超越数). The first several digits are: e= 2.718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921... where the 10 digits in bold are the answer to Google's question.
Now you are asked to solve a more general problem: find the first K-digit prime in consecutive digits of any given L-digit number.
Input Specification:
Each input file contains one test case. Each case first gives in a line two positive integers: L (≤ 1,000) and K (< 10), which are the numbers of digits of the given number and the prime to be found, respectively. Then the L-digit number N is given in the next line.
Output Specification:
For each test case, print in a line the first K-digit prime in consecutive digits of N. If such a number does not exist, output
404
instead. Note: the leading zeroes must also be counted as part of the K digits. For example, to find the 4-digit prime in 200236, 0023 is a solution. However the first digit 2 must not be treated as a solution 0002 since the leading zeroes are not in the original number.
Sample Input 1:
20 5
23654987725541023819
Sample Output 1:
49877
Sample Input 2:
10 3
2468024680
Sample Output 2:
404
Keys:
- 素数
Attention:
- int < 1e9, long long <1e18
- 注意主串长度<子串长度的情况
- s.size()返回unsigned类型,l<k时,会死循环
Code:
/*
Data: 2019-08-02 16:31:26
Problem: PAT_A1152#Google Recruitment
AC: 25:40 题目大意:
给定L位数字中找出K位的素数,前导零同样占位
*/
#include<cstdio>
#include<string>
#include<iostream>
using namespace std; bool IsPrime(string s)
{
long long n = atoll(s.c_str());
if(n== || n==)
return false;
for(int i=; i*i<=n; i++)
if(n%i == )
return false;
return true;
} int main()
{
#ifdef ONLINE_JUDGE
#else
freopen("Test.txt", "r", stdin);
#endif // ONLINE_JUDGE string s;
int l,k;
scanf("%d%d", &l,&k);
cin >> s;
for(int i=; i<=int(s.size())-k; i++)
{
if(IsPrime(s.substr(i,k)))
{
cout << s.substr(i,k).c_str();
s.clear();
break;
}
}
if(s.size() || l<k)
printf(""); return ;
}
最新文章
- Cesium原理篇:3最长的一帧之地形(2:高度图)
- 犀利的报表系统,发票据与报表开发的快速利器,AgileEAS.NET SOA中间件GReport使用指南
- python 中 深拷贝和浅拷贝的理解
- (转).Net平台开源作业调度框架Quartz.Net
- 如何把powerpoint幻灯片大小改为标准或宽屏教程【图文】
- OR查询
- 2018年最新JAVA面试题总结之JavaWeb(2)
- java mybatis后台判断表是否存在mysql
- Hdoj 1176.免费馅饼 题解
- PySide中QtGui.QFrame的用法
- TSP-UK49687
- Chrome下解决本地异步请求失败的问题(Origin null is not allowed by Access-Control-Allow-Origin. )
- delphi实现两个目录路径的链接
- 精确除法:from __future__ import division
- DAO层注入HibernateTemplate的两种方式
- To 初识Java的小菜菜们 嘻嘻~
- Logback配置讲解
- 针对SQLServer数据库的通用访问类
- 搞懂head 和 tail 命令
- mysql5.6乱码