http://acm.zzuli.edu.cn/problem.php?id=1511
题目描述
一天小P想要玩lol,但是他太菜了,必须和他的王者学长组队才能赢。
学长此时正在解一道叫loI的问题:
有N个小兵,编号为1,2,3……N,你有N种技能,第i种技能可以消灭所有编号为i+1的倍数的小兵
问最少放多少个技能可以消灭至少k个小兵
为了使小P和学长玩上lol,请你尽快解决这道题
输入
一行两个整数N,k,含义如题目描述
输出
一个整数,表示最少放多少个技能可以消灭至少k个小兵
样例输入 Copy
8 7
样例输出 Copy
4
首先肯定是用一个素数,因为如果这个数有因子的话,选它的因子可以消灭更多的小兵。
从最小的素数开始可以消灭更多的小兵, 因此可以用素数筛法来做这道题。
#include<stdio.h>
#include<string.h>
#define N 10000020
int a[N];
int main()
{
int n,k,i,j,ans,num;
while(scanf("%d%d",&n,&k)!=EOF)
{
memset(a,0,sizeof(a));
ans=0;
num=0;
a[0]=a[1]=1;
for(i=2; i<=n; i++)
{
if(num>=k)
break;
if(a[i] == 0)
{
ans++;
num++;
for(j=2*i; j<=n; j+=i)
{
if(a[j] == 0)
{
a[j] = 1;
num++;
}
}
}
}
printf("%d
",ans);
}
return 0;
}