A1152 Google Recruitment (20 point(s))

素数判断

1. 原文

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

2. 解析

截取字符串固定位数的值，判断是否为素数

:red_circle: string.substr(pos,length); 从pos位开始截取长度为length的子串

:red_circle:string转int atoi(string.c_str())

#AC代码

#include<iostream>
#include<cmath>
using namespace std;
bool isPrime(int x)
{
	if (x<2)
	{
		return false;
	}
	int sqr=sqrt(1.0*x);
	for (int i = 2; i <= sqr; ++i)
	{
		if (x%i==0)
		{
			return false;
		}
	}
	return true;
}
int main()
{
	string str;
	int n,k;
	cin>>n>>k;
	cin>>str;
	int flag=0;
	for (int i = 0; i <= n-k; ++i)
	{
		string ans=str.substr(i,k);
		int dig=atoi(ans.c_str());
		if (isPrime(dig))
		{
			flag=1;
			cout<<ans<<endl;
			break;
		}
	}
	if (flag==0)
	{
		cout<<"404"<<endl;
	}
	return 0;
}

截取到n-k为止