大家好,我们选择的是Bubble Cup比赛Div2场次的J题,不用问我Bubble Cup是什么比赛,我也不清楚。总之是一场算法比赛就是了。可能是这个比赛知名度比较低吧,参与的人数也不是很多,我们选择了一道中等通过人数的J题,作为今天的题目。
链接:https://codeforces.com/contest/1424/problem/J
这题非常不错,是一道质量很高的数学题,也很符合我的胃口。因为没有太多的trick,有的只有思维和逻辑的碰撞。
最后,附上代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include "time.h"
#include <functional>
// 一些宏定义
#define rep(i,a,b) for (int i=a;i<b;i++)
#define Rep(i,a,b) for (int i=a;i>=b;i--)
#define foreach(e,x) for (__typeof(x.begin()) e=x.begin();e!=x.end();e++)
#define mid ((l+r)>>1)
#define lson (k<<1)
#define rson (k<<1|1)
#define MEM(a,x) memset(a,x,sizeof a)
#define L ch[r][0]
#define R ch[r][1]
using namespace std;
const int N=1000050;
const long long Mod=1000000007;
int t, query[N];
int isprime[N], primecnt[N];
// 埃式筛法
void eratosthenes() {
rep(i, 0, N) isprime[i] = 1;
rep(i, 2, N) {
if (isprime[i]) {
for (int j = i+i; j < N; j += i) {
isprime[j] = 0;
}
}
}
// 维护质数的前缀和
rep(i, 2, N) {
primecnt[i] = primecnt[i-1] + isprime[i];
}
}
int main() {
eratosthenes();
scanf("%d", &t);
rep(i, 0, t) {
int query;
scanf("%d", &query);
printf("%d\n", primecnt[query] - primecnt[int(sqrt(query))] + 1);
}
return 0;
}
说到C++我想到了一个问题,之前有小伙伴问过我为什么要用Python来实现各种算法。这里刚好简单回答一下,其实没有什么原因,只是我Python用得更加顺手。C++还是当年打ACM的时候写的,之后就没怎么用过了。但不管怎么说,涉及到算法和数据结构还是C++更适合一点,这块我刚好想要听听大家的建议,大家是觉得在之后的文章当中,我是继续使用Python好呢,还是使用C++好? - END -