#include<bits/stdc++.h>
using namespace std;
bool isprime(int n)
{
	for(int i=2;i*i<=n;i++)
	{
		if(n%i==0)return 0;
	}
	return 1;
}
int main()
{
	int n;
	cin>>n;
	int cnt=0;
	for(int i=2;i<=n;i++)
	{
		if(isprime(i))cnt++;
	}
	cout<<cnt;
}

#include<bits/stdc++.h>
using namespace std;
bool prime(int a)
{
	if(a==1)
	{
		return 0;
	}
	for(int i=2;i*i<=a;i++)
	{
		if(a%i==0)
		{
			return 0;
		}
	}
	return 1;
}
int main()
{
	int n;
	cin>>n;
	int ans=0;
	for(int i=2;i<=n;i++)
	{
		if(prime(i))
		{
			ans++;
		}
	}
	cout<<ans;
	return 0;
}

是一道很水的题，用链表就能解决了，但是由于加减乘除的时间复杂度太高，所以不能一个一个判断，得用筛法。这里采用线性筛。

template <class _Tp = const unsigned long long int>
class P { _Tp *p { nullptr }; };
signed WinMain(int argv, char* argc[]) {}
#include <cstdio>
#include <ctype.h>
typedef unsigned long long ULL;
int add(int a, int b) {
	if (!a) return b;
	return add((a & b) << 1, a ^ b);
}
ULL quick_mul(int a, int b) {
	ULL res = 0;
	for (ULL t = a; b; b >>= 1, t <<= 1)
		if (b & 1) res = add(res, t);
	return res;
}
ULL square(int a) {
	return quick_mul(a, a);
}
int read() {
	char ch;
	int res = 0;
	while (!isdigit(ch = getchar()));
	res = ch ^ 48;
	while (isdigit(ch = getchar())) res = add(quick_mul(res, 10), ch ^ 48);
	return res;
}
int binary_div(int a, int b) {
	int left = -1, right = add(1ll << 31, 0xffffffff);
	while (left + 1 != right) {
		int mid = add(left, right) >> 1;
		if (quick_mul(b, mid) <= a) left = mid;
		else right = mid;
	}
	return left;
}
int mod(int a, int b) {
	return a - quick_mul(binary_div(a, b), b);
}
void print(int a) {
	if (!a) return;
	print(binary_div(a, 10));
	putchar(mod(a, 10) ^ 48);
}
struct Node {
	int dat;
	Node* next;
};
Node* create() {
	Node* head = new Node;
	head->next = nullptr;
	return head;
} 
Node* insert(Node* node, int dat) {
	Node* newNode = new Node;
	newNode->next = node->next;
	node->next = newNode;
	newNode->dat = dat;
	return newNode;
}
#define MAX_N 100005
signed main(int argv, char* argc[]) {
	int n = read();
	Node* head = create();
	Node* end = head;
	int res = 0;
	bool is_prime[MAX_N];
	for (auto& elem : is_prime) elem = true;
	for (int i = 2; i <= n; i = add(i, 1)) {
		if (is_prime[i]) {
			end = insert(end, i);
			res = add(res, 1);
		}
		for (Node* p = head->next; p; p = p->next){
			int mul = quick_mul(p->dat, i);
			if (mul > n) break;
			is_prime[mul] = false;
			if (!mod(i, p->dat)) break;
		}
	}
	print(res);
	return 0;
}

又双叒叕是一道水题

就一道水题，怎么把楼下某大佬的质数筛给轰出来了？？？
冷知识： $O(N^2)$ 也能过
详见代码：

#include<iostream>
#include<cmath>
#define QwQ return 0;
using namespace std;
int n,cnt;
int main(){
	cin>>n;
	for(int i=2;i<=n;i++){
		bool flag=true;
		for(int j=2;j<=sqrt(i);j++){
			if(i%j==0){
				flag=false;
				break;
			}
		}
		if(flag)cnt++;
	}
	cout<<cnt;
	QwQ
}

#include<bits/stdc++.h>
using namespace std;
bool IsPrime(int n){
	for(int i=2;i*i<=n;i++)if(n%i==0)return false;
	return true;
}
signed main(){
	int n,ans=0;
	cin>>n;
	for(int i=2;i<=n;i++)if(IsPrime(i))ans++;
	cout<<ans;
}

太神奇了，数据百分百超出限制了，肯定大于一万了。秀一波筛法加前缀和。

#include<bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f
using namespace std;
int n,a[150001],f[150001];
signed main(){
	for(int i=2;i<=150000;i++)
		a[i]=1;
	for(int i=2;i<=150000;i++){
		if(a[i]){
			for(int j=2;i*j<=150000;j++)
				a[i*j]=0;
		}
	}
	for(int i=1;i<=150000;i++)
		f[i]=f[i-1]+a[i];
	cin>>n;
	cout<<f[n];
	return 0;
}