文章

117

粉丝

69

获赞

860

访问

113.7k

头像
非素数个数(线性筛+前缀和)题解:
P1701 厦门大学机试题
发布于2025年2月23日 16:22
阅读数 641

#include<bits/stdc++.h>
using namespace std;

const int N = 1e7 + 10;
int l, r;
int primes[N], cnt, s[N];    
bool st[N];

void get_primes(int n)
{
	for(int i = 2; i <= n; i ++)
	{
 		if(!st[i]) primes[cnt ++] = i;
 		for(int j = 0; primes[j] <= n/ i; j ++)	
 		{
 			st[primes[j] * i] = true;
			if (i % primes[j] == 0) break; 	
		}
 	}
}

int main()
{
	get_primes(N - 10);
	
	for(int i = 1; i <= N - 10; i ++)
		s[i] += s[i - 1] + st[i];
	
	while(cin >> l >> r)
	{
		cout << s[r] - s[l - 1]<< endl;
	}
	
	return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发