90分 最后一个点TLE 萌新求助
  • 板块P3912 素数个数
  • 楼主lsxxsl
  • 当前回复10
  • 已保存回复10
  • 发布时间2021/6/22 20:46
  • 上次更新2023/11/4 21:36:22
查看原帖
90分 最后一个点TLE 萌新求助
174930
lsxxsl楼主2021/6/22 20:46

有没有大佬帮我看看,最后一个点慢的过分,怎么优化一下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll maxn = 1e8 + 1;
bool sig[maxn];
void isprime(int a)
{	
	int temp = sqrt(a);
	for(int i = 2;i <= temp;i ++)
	{
		if(sig[i] == false || (sig[i] == 0 && a % i != 0))
			continue;
		else
		{
			for(int j = 2; j <= a / i;j ++)
			{
				sig[i * j] = false;
			}
		}					
	}	
} 
int main()
{
	int n,cnt = 0;	
	memset(sig , true , sizeof(sig));
	cin>>n;	
	isprime(n);	
	for(int i = 2;i <= n;i ++)
	{
		if(sig[i] == true)
		{
			cnt ++;
		}
		else
		continue;		
	}
	cout<<cnt<<endl;
	return 0;
}


2021/6/22 20:46
加载中...