蓝桥杯_数学模板

1.试除法判定质数

#include <iostream>
using namespace std;

bool is_zs(int x)
{
    if(x<2) return false;
	
	for(int i=2;i<=x/i;i++)
		if(x%i==0)
			return false;
	return true;
}

int main()
{
	int n; cin>>n;
	
	while(n--)
	{
		int x; cin>>x;
		
		if(is_zs(x)) 
			cout<<"Yes\n";
		else
			cout<<"No\n";	
	}
	return 0;
}

2.阶乘

int fac(int x)
{
	if(x<=1) return 1;
	else return x*fac(x-1);
}

3.分解质因数

#include <iostream>
using namespace std;

void div(int x)
{
	for(int i=2;i<=x/i;i++)
	{
		if(x%i==0)
		{
			int s = 0;
			while(x%i==0) x/=i,s++;
			cout<<i<<" "<<s<<endl;
		}
	}
	
	if(x>1) cout<<x<<" "<<1<<endl;
	printf("\n");
}

int main()
{
	int n; cin>>n;
	
	while(n--)
	{
		int x; cin>>x;
		div(x);
	}
	return 0;
}

4.筛质数
4_1暴力做法(会超时)

#include <iostream>
using namespace std;

bool is_zs(int x)
{
    if(x<2) return false;
	
	for(int i=2;i<=x/i;i++)
		if(x%i==0)
			return false;
	return true;
}

int c_zs(int n)
{
	int cnt = 0;
	for(int i=1;i<=n;i++)
	{
		if(is_zs(i)) cnt++;
	}
	
	return cnt;
	
}

int main()
{
	int n; cin>>n;	
	int cnt = c_zs(n);
	cout<<cnt<<endl;
	return 0;
}

4_2(完美做法):

#include <iostream>
using namespace std;

const int N = 1000010;

int p[N],cnt;
bool st[N];

void get_zs(int n)
{
	for(int i=2;i<=n;i++)
	{
		if(st[i]) continue;
		p[cnt++] = i;
		
		for(int j=i+i;j<=n;j+=i)
			st[j] = true;
	}
}

int main()
{
	int n; cin>>n;
	
	get_zs(n);
	
	cout<<cnt<<endl;
	return 0;
}

5.试除法求约数

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
	int m; cin>>m;
	
	while(m--)
	{
		int n; cin>>n;
		
		vector<int> vt;
		
		for(int i=1;i<=n/i;i++)
		{
			if(n%i==0)
			{
				vt.push_back(i);
				if(n/i != i) vt.push_back(n/i);
			}
		}
		
		sort(vt.begin(),vt.end());
		for(int it:vt) cout<<it<<" ";
		printf("\n");
	}
	return 0;
}