当前位置：首页 > news >正文

UVa 406 Prime Cuts

news 2026/6/13 14:35:21

题目描述

题目要求从111到NNN的素数列表中，截取中心位置的一段连续素数进行输出。具体规则如下：

首先找出111到NNN之间（包含111和NNN）的所有素数。注意本题中111被视为素数。
设素数列表的长度为LLL。
如果LLL为偶数，则输出列表中心的2C2C2C个素数。
如果LLL为奇数，则输出列表中心的2C−12C - 12C−1个素数。
如果所需的中心素数数量超过了列表本身的大小，则输出整个素数列表。

输入格式

输入包含多组测试数据，每组数据占一行。每行包含两个整数NNN和CCC，其中：

NNN（1≤N≤10001 \le N \le 10001≤N≤1000）表示素数列表的上限。
CCC（1≤C≤N1 \le C \le N1≤C≤N）用于确定输出素数的数量。

输出格式

对于每组测试数据，输出一行，格式为：

N C: 素数1 素数2 素数3 ...

其中：

NNN和CCC按原值输出，后面紧跟一个冒号和空格。
输出的每个素数前面有恰好一个空格。
每组输出后面跟一个空行。

样例

输入

21218218181007

输出

212:5711182:357111818:123571113171007:1317192329313741434753596167

题目分析

本题的核心是生成111到NNN的素数列表，然后根据列表长度的奇偶性确定要输出的中心子序列。

素数的定义与范围

本题中有一个特殊规定：111被视为素数。这与通常的数学定义不同，需要注意。因此素数列表始终包含111。

NNN的最大值为100010001000，因此可以直接使用简单的素数判定方法（如试除法）来生成素数列表，无需使用复杂的筛法。

中心位置的确定

设素数列表为p[0],p[1],…,p[L−1]p[0], p[1], \ldots, p[L-1]p[0],p[1],…,p[L−1]，其中LLL为列表长度。

情况一：LLL为偶数

需要输出2C2C2C个素数。
中心位置：列表中间的两个元素是p[L/2−1]p[L/2 - 1]p[L/2−1]和p[L/2]p[L/2]p[L/2]。
从这两个元素向两侧扩展，共输出2C2C2C个元素。
起始索引为start=L/2−C\textit{start} = L/2 - Cstart=L/2−C，结束索引为end=L/2+C−1\textit{end} = L/2 + C - 1end=L/2+C−1。

情况二：LLL为奇数

需要输出2C−12C - 12C−1个素数。
中心位置：列表中间的元素是p[(L−1)/2]p[(L-1)/2]p[(L−1)/2]。
从这个元素向两侧扩展，共输出2C−12C - 12C−1个元素。
起始索引为start=(L−1)/2−(C−1)\textit{start} = (L-1)/2 - (C - 1)start=(L−1)/2−(C−1)，结束索引为end=(L−1)/2+(C−1)\textit{end} = (L-1)/2 + (C - 1)end=(L−1)/2+(C−1)。

边界处理

如果计算出的start<0\textit{start} < 0start<0或end≥L\textit{end} \ge Lend≥L，说明需要的中心素数数量超过了列表大小，此时应输出整个列表（即从p[0]p[0]p[0]到p[L−1]p[L-1]p[L−1]）。

特殊情况

当CCC足够大时，2C2C2C或2C−12C - 12C−1可能超过LLL，此时直接输出整个列表。
注意CCC的取值范围是1≤C≤N1 \le C \le N1≤C≤N，但NNN可能小于LLL（例如N=1N=1N=1时L=1L=1L=1），此时CCC可能大于LLL，需要正确处理。

由于NNN最大为100010001000，且输入包含多组数据，可以预先计算出111到100010001000的所有素数，存储在全局数组中。这样每组测试数据只需从预先生成的素数表中截取111到NNN的部分即可。

素数判定使用试除法：对于每个数xxx（2≤x≤10002 \le x \le 10002≤x≤1000），检查是否存在222到x\sqrt{x}x之间的因子。如果没有，则xxx是素数。同时将111也加入素数列表。

对于每组输入的NNN和CCC：

从预先生成的素数表中，取出所有≤N\le N≤N的素数，得到当前列表。
设列表长度为LLL。
计算需要输出的数量KKK：
- 若LLL为偶数，则K=2CK = 2CK=2C。
- 若LLL为奇数，则K=2C−1K = 2C - 1K=2C−1。
如果K≥LK \ge LK≥L，则输出整个列表。
否则，计算起始索引：
- 若LLL为偶数：start=L/2−C\textit{start} = L/2 - Cstart=L/2−C
- 若LLL为奇数：start=(L−1)/2−(C−1)\textit{start} = (L-1)/2 - (C - 1)start=(L−1)/2−(C−1)
输出从start\textit{start}start到start+K−1\textit{start} + K - 1start+K−1的所有素数。

输出时严格按照格式：先输出NNN和CCC，中间用一个空格分隔，然后输出冒号和空格，接着输出每个素数，每个素数前面有一个空格。输出结束后打印一个空行。

代码实现

// Prime Cuts// UVa ID: 406// Verdict: Accepted// Submission Date: 2016-07-20// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intprimes[200],cnt=0;voidgenerate_primes(){primes[cnt++]=1;for(inti=2;i<=1000;i++){boolis_prime=true;for(intj=2;j<=sqrt(i);j++){if(i%j==0){is_prime=false;break;}}if(is_prime)primes[cnt++]=i;}}intmain(intargc,char*argv[]){generate_primes();intN,C;while(cin>>N>>C){vector<int>selected;for(inti=0;i<cnt&&primes[i]<=N;i++)selected.push_back(primes[i]);intsize=selected.size();cout<<N<<' '<<C<<':';if(size%2==1){intneed=2*C-1;if(need>=size){for(inti=0;i<size;i++)cout<<' '<<selected[i];}else{intstart=size/2-(C-1);for(inti=start;i<start+need;i++)cout<<' '<<selected[i];}}else{intneed=2*C;if(need>=size){for(inti=0;i<size;i++)cout<<' '<<selected[i];}else{intstart=size/2-C;for(inti=start;i<start+need;i++)cout<<' '<<selected[i];}}cout<<"\n\n";}return0;}