专栏文章

P12138题解

llyxqqq1
P12138题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipn2mw3
此快照首次捕获于
2025/12/03 14:41
3 个月前
此快照最后确认于
2025/12/03 14:41
3 个月前
查看原文

P12138

这题蛮简单的
一个正整数只能被 1 和它本身两个数整除，就称为一个质数
众所周知，我们可以循环一个数X的前X-2个数，如果X可以整除这个数，那么它就不是质数，反之它只能被 1 和它本身两个数整除就是质数
可是它如果循环了每一个数太费时了，4%2==4%4 6%3==6%6 5%2==5%4 将一个长X数轴折叠，一一对应的数被X%的值相同
注：xx % yy（mod）是x除y的余数
无优化代码
CPP
bool sushu(int x)
{
	if(x<2)
		return 0;
	for(int i=2;i<x;i++)
		if(x%i==0)
			return 0;
	return 1;
```cpp
bool sushu(int x)
{
	if(x<2)
		return 0;
	for(int i=2;i<x;i++)
		if(x%i==0)
			return 0;
	return 1;
}
优化代码
CPP


bool sushu(int x)
{
	if(x<2)
		return 0;
	for(int i=2;i<=sqrt(x);i++)
		if(x%i==0)
			return 0;
	return 1;
}
AC代码：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int p=0;
bool sushu(int x)
{
	if(x<2)
		return 0;
	for(int i=2;i<=sqrt(x);i++)
		if(x%i==0)
			return 0;
	return 1;
}
signed main()
{
	for(int i=1;;i++)
	{
		if(sushu(i))
		{
			p++;
			if(p==2025)
			{
				cout<<i;
				return 0;
			}
		}
	}
	return 0;
}

输出17609

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...