PAT 1152 Google Recruitment (20 分)-甲级

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

题目大意:给出一个l长度的字符串,求出其中第一个k位的素数
分析: 枚举每个k位的子串,转换成整数,判断是否是素数(判断素数的时候要把0和1也考虑进去)~

 

[note] Homebrew的介绍、安装方法与常用命令整理

Homebrew介绍:
Homebrew是Mac下一款软件包管理器(软件包管理系统:在计算机中自动安装、配置、卸载和升级软件包的工具组合),可以简化macOS上软件的安装管理过程。Homebrew Cask是建立在Homebrew基础之上的可视化图形界面软件的安装工具,是Homebrew的扩展。

使用Homebrew的好处:
一条命令行命令即可安装软件;下载的软件来源于软件官网,更安全;软件的更新与卸载更方便;Homebrew中的软件版本一般比Mac App Store的版本新;所有安装包都放在一个地方,便于管理。

Homebrew的安装方法:
Mac系统升级到OS X 10.9以上;
到Mac App Store安装XCode;
在命令行中输入以下命令安装Homebrew:
/usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"

Homebrew的常用命令:
brew search 关键字查找与关键字有关的软件
brew cask install 软件名:安装软件
brew cask uninstall 软件名:卸载软件
brew cask info 软件名:显示该软件的信息
brew cask list:列出所有通过Homebrew Cask安装的软件
brew outdated:检查可更新的应用有哪些
brew upgrade:将所有软件更新到最新版
brew upgrade 软件名:只更新该软件到最新版
brew cleanup:把所有应用的旧版本和缓存删除
brew cleanup 软件名:只清除该软件的旧版本和缓存
brew home 软件名:打开该软件的官网
brew cask update:更新Homebrew Cask
brew cask help:查看帮助

[note] 使用LaTeX公式表示常用数学符号整理

使用 $...$ 插入行内inline公式,使用两个插入行间公式 $$...$$\quad 代表当前字体下一个汉字的空白距离,  \qquad 代表当前字体下两个汉字的空白距离, \, 表示空格, \\ 表示换行

^ 表示上标, _ 表示下标,默认作用之后的一个字符,如果是连续的几个字符,需要用 {} 花括号括起来

如输入: e=mc^2 \qquad a_{ij} \qquad x_2^5

显示为:

\alpha 、 \beta 、 \gamma 、 \delta 、 \theta 、 \lambda 、 \mu 、 \nu 、 \xi 表示小写希腊字母α、β、γ、δ、θ、λ、μ、ν、ξ(如果第一个字母大写表示对应的大写希腊字母,如 \Alpha 、 \Beta 、 \Gamma 、 \Delta 表示:Α、Β、Γ、Δ

如输入: \alpha \beta \gamma \delta \epsilon \zeta \eta \theta \qquad \iota \kappa \lambda \mu \nu \omicron \xi \pi \qquad \rho \sigma \tau \upsilon \phi \chi \psi \omega \qquad \varepsilon \digamma \varkappa \varpi \qquad \varrho \varsigma \vartheta \varphi

显示为:

= 、 \neq 、 \equiv 分别表示:=、≠、≡

\becasue 表示因为符号∵, \therefore 表示所以符号∴

\sqrt 表示平方根, \sqrt[n] 表示n次方根, \vec{a} 表示向量a, \overrightarrow{a b} 表示向量ab, \overleftarrow{a b} 与 \overleftarrow{a b} 箭头方向相反, \ldots 表示处于下方位置的三个点 ... , \cdots 表示处于中间位置的三个点…, \vdots 是竖着的三个点, \ddots 是斜着的三个点, \overbrace 表示上大括号, \underbrace 表示下大括号, \overline 表示上划线, \underline 表示下划线

如输入: y=x^3+e^{x^2}-x^{-\alpha t}-\sqrt[4]{x} \qquad a_{ij} \neq a_{ji} \qquad \overline{x+y} \qquad \underbrace{1+2+\cdots+n}_n \qquad \overrightarrow{a b}

显示为:

x^\prime 表示x的导数x’,也可以用 x' 表示, \partial 表示偏微分符号∂, \to 表示向右短箭头, \longrightarrow 表示向右长箭头, \infty 表示无穷符号∞, \pm 表示±, \mp 表示∓, \div 表示除法符号÷ , \in 表示属于符号∈, \notin 表示不属于符号∉, \subseteq 表示子集符号⊆, \sim 表示相似符号∽, \approx 表示约等于符号≈, \le 表示小于等于符号, \ge 表示大于等于符号, \perp 表示垂直符号⊥

如输入: f^{(3)}=x''+x'+y^\prime+y \qquad n\to\infty \qquad a\pm b \qquad a\in b \qquad a\notin b \\ A\subseteq B \qquad sinx\sim x \qquad a+b\le c \qquad ab\perp cd

显示为:

\frac{...}{...} 表示分数, \int 表示积分运算符, \lim 表示极限运算符, \iint 表示二重积分, \iiint 表示三重积分, \iiiint 表示四重积分, \oint 表示闭合的曲线曲面积分, \sum 表示求和运算符, \prod 表示乘积运算符, \bigcap 表示交集, \bigcup 表示并集

如输入: \lim_{n \to \infty}\frac{sinx}{1+\frac{1+x}{e+x^2}} \qquad \int_{a}^{b}e^x\,\mathrm{d}x \qquad \iint_{D}^{W}\,\mathrm{d}x\,\mathrm{d}y \qquad \iiint \qquad \oint \qquad \bigcap \qquad \bigcup

显示为:

如输入: \iint_\Sigma(P cos\alpha + Q cos\beta + R cos \gamma) \mathrm dS = \iiint_\Omega(\frac{\partial P}{\partial x} + \frac{\partial Q}{\partial y} + \frac{\partial R}{\partial z}) \mathrm d\nu

显示为:

\forall 表示任意的符号∀, \exists 表示存在符号∃, \Rightarrow 表示推出符号⇒, \Leftarrow 是向左的推出符号, \Leftrightarrow 是等价于符号⇔

如输入: \because \forall\, x \in [a, b], \exists \, y \in \mathrm{R} \therefore M \Leftrightarrow N

显示为:

矩阵的每一行元素用 & 分隔,这样它们就能上下对齐,并在头尾加上 \begin{...} 和 \end{...} ,…处可以为matrix、vmatrix、Vmatrix、bmatrix、Bmatrix、pmatrix等

如输入: \begin{matrix} x & y \\ z & v \end{matrix} \qquad \begin{vmatrix} x & y \\ z & v \end{vmatrix} \qquad \begin{Vmatrix} x & y \\ z & v \end{Vmatrix} \qquad \begin{bmatrix} 0 & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & 0 \end{bmatrix} \qquad \begin{Bmatrix} x & y \\ z & v \end{Bmatrix} \qquad \begin{pmatrix} x & y \\ z & v \end{pmatrix}

显示为:

\begin{...} 和 \end{...} 的…处写 cases 会变成方程组的花括号形式

如输入: \begin{cases} 3x + 5y + z \\ 7x - 2y + 4z \\ -6x + 3y + 2z \end{cases}

显示为:

【C、C++】ctype.h、cctype中的isnumber()函数和isdigit()函数的区别

Mac OS X 手册页上ctype函数中对isnumber()和isdigit()函数的区别是这样解释的:

The isnumber() function behaves similarly to isdigit(), but may recognize additional characters, depending on the current locale setting. 

也就是说:isnumber()函数与isdigit()相似,但isnumber()可能会识别其他字符,具体取决于当前的区域设置~

在XCode或者CLion(Mac版)的ctype.h(或者cctype)中可能会见到isnumber()函数,然而查阅C++官方文档却找不到,这是因为isnumber()并不是C/C++的官方库函数,而是Apple特地为Mac OS的C++添加的它认为好用的一些函数(这些函数有很多,不止isnumber)。可以查看Mac OS X Man Pages中ctype函数页找到isnumber()函数~手册中也提到isnumber()并不在C90标准中:

These functions, except for digittoint(), isascii(), ishexnumber(), isideogram(), isnumber(), isphonogram(), isrune(), isspecial() and toascii(), conform to ISO/IEC 9899:1990 (ISO C90”).

可以看到如果使用isnumber()函数在Linux环境下g++是无法编译通过的:

在Clang下也是无法编译通过的:

所以isnumber()并不是标准的C/C++库函数,如果是刷算法的时候还是不要使用哦~