文章

13

粉丝

120

获赞

4

访问

15.2k

头像
判断素数 题解:
P1013 贵州大学机试题
发布于2023年5月4日 18:49
阅读数 2.1k

素数的定义:大于1的整数中,只能被1和这个数本身整除的数

 

试除法判断质数

	auto cal = [&](int x) -> bool
	{
		if(x < 2)return false;
		for(int i = 2;i <= sqrt(x);i++)
		{
			if(x % i == 0 )return false;
		}
		return true;
	};

时间复杂度:O(sqrt(n))

AC代码

#include <bits/stdc++.h>


#define fi first
#define endl '\n'
#define se second
#define pp pop_back
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define all(a) begin(a),end(a)
#define lp(i,j,k) for(int i=int(j);i<=int(k);i++)
#define rlp(i,j,k) for(int i=int(j);i>=int(k);i--)
#define IO std::ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);

using namespace std;
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

template <class T> inline void chkmax(T &x,T y) {if(x<y) x=y;}
template <class T> inline void chkmin(T &x,T y) {if(x>y) x=y;}

const ll mod = 1e9 + 7;
const int N = 1e6 + 10;
const int ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发