当前位置:网站首页>WUSTOJ:n个素数构成等差数列
WUSTOJ:n个素数构成等差数列
2022-08-09 10:13:00 【Simonqwer】
WUSTOJ:n个素数构成等差数列
Time Limit: 1 Sec
Memory Limit: 128 MB
64bit IO Format: %lld
Description
有n个素数(均小于m)可以构成一个等差数列。请编写程序根据给定的n和m,统计出满足条件的解有多少种。
例如,n=3,m=10;即在1到10的范围内有3个素数构成等差数列的情况有几组解,很显然3,5,7是一组解,也是唯一的一组。
提示:main函数已经给出(如下所示),提交时不必提交下面的代码,只需要提交你自己添加的代码。
#include<stdio.h>
int main()
{
int n,m,t;
while(scanf("%d%d",&m,&n)!=EOF)
{
t=f(m,n);
printf("%d\n",t);
}
return 0;
}
Input
包含多组测试数据,每组测试数据占一行,每行2个正整数,分别代表n和m,其中n大于等于3且小于等于10,m小于等于1000。
Output
每组测试数据输出占一行,每行输出一个整数,即满足条件的解的组数。
Sample Input
3 10
Sample Output
1
作答
选用C语言作答
分析
- 因为数据有界,首先可以把1000以内的素数进行打表,利用数组存储,节省计算时间。
- 在查找的过程中一定牵扯到遍历的方法,要选取适当的方法减少计算时间。
- 通过查询可知1000以内的素数共有168个,这里我将a[0]=0是为了数组的下标和素数相对应。并且可以得出结论等差数列的公差d最大为997-2=995(以首位素数差当作界点的最大公差)。项数为3,公差最小的等差数列为(3,5,7),此时公差为2。整个过程中满足,2<=d<=995,压缩d的取值区间。
int a[169]={
0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,
113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,
239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,
373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,
503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,
647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,
809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,
953,967,971,977,983,991,997};
- 利用数组下标表示素数,用(0,1)区分是否为素数
int b[1001];
for(i=1;i<=1000;i++)
b[i]=0;
for(i=1;i<=168;i++)
b[a[i]]=1;
- 使用while语句进行状态读取,即‘ 0 ’为非素数,‘ 1 ’为素数,并且沿顺序继续读取下去。同时在扫描素数的时候,可以减少最后一组等差数列判断,即只扫到169-m即可。
- 因为要求的等差数列有项数要求,所以用计数器,我这里用的是count。
- 题目的m,n有点混乱,注意辨析。
源码
int f(int m,int n)
{
int a[169]={
0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,
113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,
239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,
373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,
503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,
647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,
809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,
953,967,971,977,983,991,997};
int i;
int b[1001];
for(i=1;i<=1000;i++)
b[i]=0;
for(i=1;i<=168;i++)
b[a[i]]=1;
int j,count,d,sum=0;
for(i=1;i<=169-m;i++)
{
d=2;
while(d<=995)
{
count=0;
j=a[i];
while(b[j]==1 && j<=n)
{
if(count<m)
count++;
if(count==m)
{
sum++;
break;
}
j += d;
}
d++;
}
}
return sum;
}
ps:在c语言的情况下,这个思路出奇的相同(通过和学长的交流知道)。如果有更好的,不超时的,ac过的代码,欢迎来踹我。
边栏推荐
猜你喜欢
随机推荐
MySQL备份与恢复
2021-01-11-雪碧图做表情管理器
学长告诉我,大厂MySQL都是通过SSH连接的
EndNote使用指南
程序员的专属浪漫——用3D Engine 5分钟实现烟花绽放效果
tuple dictionary collection
LeetCode56:合并区间 C语言解法,注解详细 一看就懂!
LeetCode148:排序链表 归并排序,思路清晰,C语言练习看过来!
分类预测 | MATLAB实现CNN-LSTM(卷积长短期记忆神经网络)多特征分类预测
从源码分析UUID类的常用方法
Win系统 - 罗技 G604 鼠标蓝灯闪烁、失灵解决方案
MySQL索引、视图、设计三范式,通俗易懂,不可错过!
[Halcon&几何] 直线的垂线与延长线的计算
【size_t是无符号整数 (-1 > 10) -> 1】
Super detailed MySQL basic operations
多线程(基础)
Loop nesting and basic operations on lists
[贴装专题] 基于多目视觉的手眼标定
Celebrate ranked 18
libavcodec.dll导致游戏不能运行及explorer关闭