题解 - 【入门】判断质数

9

hetao794786 LV 10 @ 2022-8-17 21:43:11

今天这题是简单的循环，我看了题解，发现都太复杂了，我来发发思路吧~

首先遍历从 2 ~ n - 1，也就是如果能整除就不是质数的循环
每一次都判断一次 n % i 是否等于 0
成立：直接输出（因为已经是最小约数了），并且结束代码
不成立到最后的：输出“Yes”就好啦~

上代码吧~（AC过~）

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, s = 1;
    cin >> n;
    for (int i = 2; i <= n - 1; i++)
    {
        if (n % i == 0)
        {
            cout << i;
            return 0;
        }
    }
    cout << "Yes";
    return 0;
}

hetao79152 @ 2022-8-22 13:57:09

时间复杂度太高
hetao81824 @ 2022-8-30 16:49:55

int s = 1多余
hetao2909373 @ 2022-11-20 15:51:18

赞同@
hetao2909373 @ 2022-11-20 15:53:55

i <= n - 1可以化简为i < n.
hetao4976191 @ 2023-2-24 21:30:26

挑毛病社团来了
hetao794786 @ 2023-8-12 18:30:53

本人全身都是刺是吧（一笑而过）
hetao1380059 @ 2023-8-14 21:43:24
可以把for (int i = 2; i <= n - 1; i++) 改成
```
for(int i=2;i*i<=n;i++)
```
时间复杂度可以降低

8

hetao2909373 LV 9 @ 2022-11-20 16:15:32

几种方法供大家选择： ①无函数无num：

#include <iostream>
using namespace std;
int main()
{
    int x;
    cin >> x;
    for (int i = 2; i < x; i++)
    {
        if (x % i == 0)
        {
            cout << i;
            return 0;
        }
    }
    cout << "Yes";
    return 0;
}

②无函数有num：

#include <iostream>
using namespace std;
int num = 0;

int main()
{
    int x;
    cin >> x;
    for (int i = 2; i < x; i++)
    {
        if (x % i == 0)
        {
            cout << i;
            num++;
            break;
        }
    }
    if (num == 0)
    {
        cout << "Yes";
    }
    return 0;
}

③无函数有bool：

#include <iostream>
using namespace std;
int main()
{
    int x;
    cin >> x;
    bool flag = true;
    for (int i = 2; i < x; i++)
    {
        if (x % i == 0)
        {
            cout << i;
            flag = false;
            break;
        }
    }
    if (flag)
    {
        cout << "Yes";
    }
    return 0;
}

④有函数（void）：

#include <iostream>
using namespace std;
void prime(int x)
{
    bool flag = true;
    for (int i = 2; i < x; i++)
    {
        if (x % i == 0)
        {
            cout << i;
            flag = false;
            break;
        }
    }
    if (flag)
    {
        cout << "Yes";
    }
}
int main()
{
    int y;
    cin >> y;
    prime(y);
    return 0;
}

⑤时间复杂度：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
int n, pri[MAXN], cnt;
bool vis[MAXN];
void Euler()
{
    for (int i = 2; i < MAXN; ++i)
    {
        if (!vis[i])
        {
            pri[cnt++] = i;
        }
        for (int j = 0; j < cnt; ++j)
        {
            if (1ll * i * pri[j] >= MAXN)
            {
                break;
            }
            vis[i*pri[j]] = 1;
            if (i % pri[j] == 0)
            {
                break;
            }
        }
    }
    vis[0] = vis[1] = 1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Euler();
    cin >> n;
    if (!vis[n])
    {
        cout << "Yes";
        return 0;
    }
    else
    {
        for (int i = 2; i <= n; i++)
        {
            if (n % i == 0)
            {
                cout << i;
                return 0;
            }
        }
    }
    return 0;
}

以上几种方法都是AC过的，大家可以选择自己理解的方法来编。

hetao4976191 @ 2023-2-24 21:29:29

无意冒犯，但第五种好像和@黄钰轩（幻想一笑而过）写的欧拉筛一毛一样啊

hetao8554411 @ 2023-3-6 18:35:57

补充： ⑥作弊

#include <bits/stdc++.h>
using namespace std;
int main()
{
    cout << "Yes";
    return 0;
}

（开个doge，别踩）

hetao1739244 @ 2023-3-27 15:58:33

6@
hetao269430 @ 2023-4-22 21:03:55

作弊大师。。。@

4

幻想一笑而过 LV 9 @ 2022-8-8 19:40:35

高级写法欧拉筛时间复杂度O(n);

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+5;
int n,pri[MAXN],cnt;
bool vis[MAXN]; // 如果a是素数，则vis[a]==false / vis[a]==0;
void Euler(){ // 欧拉筛
    for(int i=2;i<MAXN;++i){
        if(!vis[i])pri[cnt++]=i;
        for(int j=0;j<cnt;++j){
            if(1ll*i*pri[j]>=MAXN)break;
            vis[i*pri[j]]=1;
            if(i%pri[j]==0)break;
        }
    }
    vis[0]=vis[1]=1;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Euler();
    cin>>n;
    if(!vis[n]){
        cout<<"Yes";
        return 0;
    }else{
        for(int i=2;i<=n;i++){
            if(n%i==0){
                cout<<i;
                return 0;
            }
        }
    }
    return 0;
}

hetao794786 @ 2022-8-17 21:40:41

可以是可以，但是希望你能然读者看懂（我看懂了）
hetao4976191 @ 2023-2-24 21:22:45

@我没懂
hetao6345164 @ 2023-3-25 11:46:19

看不懂，能用简单一点的方法吗
hetao10524952 @ 2023-8-1 15:26:30

@666
hetao3604134 @ 2024-1-31 14:46:25

你确定是“希望然读者看懂了”？@

2

binger LV 8 @ 2022-9-22 21:32:08

看了下其他的写法，要么太难理解要么时间复杂度太高，我这里有个简单点的

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    bool f = true;
    cin >> n;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            f = false;
            cout << i;
            break;
        }
    }
    if (f)
    {
        cout << "Yes";
    }
    return 0;
}

1

hetao5161725 LV 10 @ 2023-11-25 14:26:04

#include <iostream>
using namespace std;
int main()
{
    int n, x, sum = 0;
    cin >> n;
    for (int i = 2;i <= n - 1;i++)
    {
        if (n % i == 0)
        {
            x = i;
            sum++;
            break;  // 跳出循环
        }
    }
    if (sum == 0)
    {
        cout << "Yes";
    }
    else
    {
        cout << x;
    }
    return 0;
}

1

hetao1445912 LV 8 @ 2022-9-17 21:36:11

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+5;
int n,pri[MAXN],cnt;
bool vis[MAXN]; // 如果a是素数，则vis[a]==false / vis[a]==0;
void Euler(){ // 欧拉筛
    for(int i=2;i<MAXN;++i){
        if(!vis[i])pri[cnt++]=i;
        for(int j=0;j<cnt;++j){
            if(1ll*i*pri[j]>=MAXN)break;
            vis[i*pri[j]]=1;
            if(i%pri[j]==0)break;
        }
    }
    vis[0]=vis[1]=1;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Euler();
    cin>>n;
    if(!vis[n]){
        cout<<"Yes";
        return 0;
    }else{
        for(int i=2;i<=n;i++){
            if(n%i==0){
                cout<<i;
                return 0;
            }
        }
    }
    return 0;
}

hetao2909373 @ 2022-11-20 16:16:20

似曾相识的感觉
hetao4976191 @ 2023-2-24 21:31:17

@ 我见过三遍了

0

hetao1938966 LV 8 @ 2024-5-4 21:04:30

看了一下题解，发现都太复杂了。

（AC）

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	bool f = true;
	cin >> n;
	for (int i = 2;i * i <= n;i++)
	{
		if (n % i == 0)
		{
			f = false;
			cout << i;//输出除1以外的最小因数 
			break;//退出循环 
		}
	}
	if (f)
	{
		cout << "Yes" << endl;
	}
	return 0;
}

（doge）

#include <bits/stdc++.h>
using namespace std;
int main()
{
	cout << "Yes";
	return 0;
}

0

hetao5326026 LV 9 @ 2024-2-19 18:15:33

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int x;
    cin >> x;
    for (int i = 2; i < x; i++)
    {
        if (x % i == 0)
        {
            cout << i;
            return 0;
        }
    }
    cout << "Yes";
    return 0;
}

0

hetao4805150 LV 10 @ 2024-1-31 11:41:18

#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
for (int i=2;i<n;i++)//判断除了1和数本身有没有因数
{
if (n%i==0)
{
cout << i;
return 0;//如果不是质数，结束运行
}
}
cout << "Yes";//如果是质数，输出Yes
return 0;
}

0

hetao2967233 LV 8 @ 2024-1-16 19:38:51

7???

cout  <<"我不懂！！！";

0

hetao283990 LV 4 @ 2024-1-14 11:57:13

非常简单！！Python

a = int(input())
s = 'Yes'
for i in range(2,a+1):
    if a % i == 0 and a != i:
        s = i
        break
print(s)

0

hetao1938355 LV 5 @ 2024-1-13 21:05:51

#include<bits/stdc++.h>
using namespace std;
int isprime(int n){
    for(int i=2;i<sqrt(n);i++){
        if(n%i==0){
            return i;
        }else{
            continue;
        }
    }
    return 1;
}
    
int main(){
    int n;
    cin>>n;
    if(isprime(n)==1){
        cout<<"Yes";
    }else{
        cout<<isprime(n);
    }
    return 0;
}//100%AC,请放心食用：）

0

hetao1846737 LV 10 @ 2023-8-31 11:51:53

过辣！

要不是输出第2个因数，我也不至于用ans……

    int n;
    cin>>n;
    int ans[n+1];
    for (int i=0;i<=n;i++)ans[i]=0;
    for (int i=1;i<=n;i++)if (n%i==0)ans[i]=i;
    for (int i=1;i<=n;i++)
    {
        if (ans[i]>0)
        {
            if (ans[i]!=1 && ans[i]!=n)
            {
                cout<<ans[i];
                return 0;
            }
        }
    }
    cout<<"Yes";

0

hetao10292628 LV 9 @ 2023-8-10 19:48:44

#include <iostream>
using namespace std;
int main()
{
    cout << "Yes";
    return 0;
}
已AC
最短```

0

hetao523822 LV 10 @ 2023-6-24 12:07:24

#include <iostream>
using namespace std;
int main()
{
    int h = 0,l;
    cin >> l;
    for (int i = 2;i < l;i++)
    {
        if (l % i == 0 && h == 0)
        {
            h = i;
            break;
        }
    }
    if (h == 0)
    {
        cout << "Yes";
    }
    else
    {
        cout << h;
    }
}//时间复杂度O（n）<2.5ms

0

hetao269430 LV 7 @ 2023-4-22 21:02:34

比较简单，用bool变量记录是否是素数，不是的话将bool设为false（默认为true），输出i，break。是的话最后的if就会为true输出Yes。

int n;
    bool flag = true;
    cin>>n;
    for(int i = 2 ; i < n ; i++)
    {
        if(n % i == 0)
        {
            cout<<i;
            flag = false;
            break;
        }
    }
    if(flag)
    {
        cout<<"Yes";
    }
核心代码如上（套个#include<>基本的头文件即可运行，已AC（建议用#include<bits/stdc++.h>)

-1

hetao28428387 LV 10 @ 2024-2-26 17:05:50

最长代码和最短代码:

// 最长代码:
#include <bits/stdc++.h>

using namespace std ;

const int MAXN = 1e6 + 5;

int n, pri[MAXN], cnt;

bool vis[MAXN];

void Euler()

{

for (int i = 2; i < MAXN; ++i)

{


if (!vis[i])

{

pri[cnt++] = i;



}

for (int j = 0; j < cnt; ++j)

{


if (1ll * i * pri[j] >= MAXN)

{

break;



}

vis[i*pri[j]] = 1;

if (i % pri[j] == 0)

{

break;



}



}



}

vis[0] = vis[1] = 1;

}

int main()

{


ios::sync_with_stdio(false);

cin.tie(0);

cout.tie(0);

Euler();

cin >> n;

if (!vis[n])

{


cout << "Yes";

return 0;



}

else

{

for (int i = 2; i <= n; i++)

{


if (n % i == 0)

{


cout << i;

return 0;


}


}



}

return 0;

}
// 最短代码
#include<iostream>
int main(){std::cout<<"Yes";}

hetao28428387 @ 2024-2-26 17:08:02

请大佬们数一数最长的和最短的各有几行
hetao28428387 @ 2024-2-26 17:11:57

参考答案: 最长的AC代码有105行, 最短的AC代码有2行.

-1

hetao9499759 LV 8 @ 2023-12-18 20:41:25

#include<iostream>
using namespace std;
int main(){
	int n;
	cin>>n;
	for(int i=2;i<n;i++){
		if(n%i==0){
			cout<<i;
			return 0;
		}
	}
	cout<<"Yes";
	return 0;
}

-1

hetao348339 LV 10 @ 2023-12-12 18:38:42

print("YES")

-1

hetao15155991 LV 8 @ 2023-11-4 20:46:47

最短代码

#include <iostream>
using namespace std;
int main()
{
    cout<<"Yes";
    return 0;
}

25 条题解

非常简单！！Python

【入门】判断质数

信息

状态

开发

支持

25 条题解

非常简单！！Python

【入门】判断质数

信息

状态

开发

支持

还没有账户？

登录