首页 > 试题广场 >

素数判断

[编程题]素数判断
  • 热度指数：49419 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}给定 T 个正整数 n，判断每个 n 是否为素数。

【名词解释】
\hspace{15pt}素数：大于 1 且仅能被 1 和自身整除的正整数。

输入描述:
\hspace{15pt}第一行输入一个整数 T（1 \leqq T \leqq 10），表示需要判断的整数个数。

\hspace{15pt}接下来 T 行，每行输入一个正整数 n（1 \leqq n \leqq 10^5）。


输出描述:
\hspace{15pt}输出 T 行，每行对应一个测试用例：若 n 是素数，输出 \text{Yes}；否则输出 \text{No}。
示例1

输入

2
1
2

输出

No
Yes

说明

第一个测试用例 n=1，1 不是素数，输出 No；第二个测试用例 n=2，2 是素数，输出 Yes。
算法知识视频讲解
添加回答
董佳俊头像 董佳俊
#include <stdio.h>
int isPrime(int n) {
    if (n <= 1) {
        return 0;
    }
    if (n == 2) {
        return 1;
    }
    for (int i = 2; i < n; i++) {
…    return 0;
}
发表于 2025-09-23 22:36:23 回复(0)
C++
凉皮真好吃头像 凉皮真好吃
#include <bits/stdc++.h>
using namespace std;

int main() {
   int t,n,a;
   cin>>t;

   for (int i=1;i<=t;i++){
    cin>>n;
    a=0;
    for (int j=2;j<n;j++){
        if(n%j==0)
        a=1;
       
    }
   
       if(a==1||n==1)
       cout<<"No"<<endl;
       else
        cout<<"Yes"<<endl;
   
   }

}
发表于 2025-10-02 15:23:47 回复(1)
Python3
勤劳的大魔王只想搞钱头像 勤劳的大魔王只想搞钱
t = int(input())
for i in range(t):
    n = int(input())
    s = False
    if n==1:
        print('No')
        continue
    if n==2:
        print('Yes')
        continue
    for j in range(2,n):
        if n%j==0:
            s = True
            break
    print('No') if s else print('Yes')
   
发表于 2025-07-13 23:08:42 回复(0)
C++
计应3254沈楚涵程头像 计应3254沈楚涵程 
bool p(int n) {
    if(n < 2) return false;
    for(int i = 2; i * i <= n; i ++) if(n % i == 0) return false;
    return true;
}
int main() {
    int t;
    cin >> t;
    while(t --) {
        int n;
        cin >> n;
        cout << (p(n) ? "Yes" : "No") << endl;
    }
}

发表于 2025-12-13 13:53:19 回复(0)
C
小二的酒头像 小二的酒
#include<stdio.h>
#include<math.h>
int isprime(int n)
{
    if(n<=1)
    return 0;
    if(n<=3)
    return 1;
    if(n%2==0||n%3==0)
    return 0;
    for(int i=5;i*i<=n;i=6+i)
    {
        if(n%(i+2)==0||n%i==0)
        return 0;
    }
            return 1;
        }
int main()
{
    int n,num[10];
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&num[i]);
    }
    for(int i=0;i<n;i++)
    {
    if(isprime(num[i]))
    {printf("Yes\n");}
    else{
        printf("No\n");
    }}
    return 0;
    }
if(n<=1)比较复杂的位置在于函数，素数的判断要是规律总结得当，会发现其实都是6k+1或者6k-1，剩下的就是照着这个思路去编写，主函数正常按照思路编写即可

发表于 2025-12-19 21:22:22 回复(0)
C++
LiLvShai头像 LiLvShai 
#include <iostream>
using namespace std;

int main() {
  int t;cin>>t;
  for (int i=1; i<=t; i++) {
    int n;
    cin>>n;

    int a=-2;//每个数都会被1和自己除（两次），刚好数字1只会被除1次，a变成-1不等于0，输出为No
    for(int j=1;j<=n;j++)
    {
      if(n%j==0)
      {
        a++;
      }
    }

    cout<<(a==0?"Yes":"No")<<endl;

  }
    
}
让n被从1到n的每一个数除
发表于 2025-11-25 00:27:19 回复(0)
C++
喜欢后撤步的小太阳等一个offer头像 喜欢后撤步的小太阳等一个offer
#include <bits/stdc++.h>
using namespace std;
bool isprime(int x){
    if(x<2)
        return false;
    for(int i=2;i<=sqrt(x);i++){
        if(x%i==0){
            return false;
        }
    }
    return true;
}

int main() {
    int T,x,p;
    int t[101];
    cin>>T;
    p=T;
    for(int i=0;p>0;p--,i++){
        cin>>x;
        t[i]=x;
    }
    for(int j=0;j<T;j++)
        if(isprime(t[j]))
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
}
发表于 2025-11-12 00:30:31 回复(0)
Python3
意若久时天然呆头像 意若久时天然呆 
T=int(input())
p=1<=T<=10
if p:
    for i in range(T):
        p3=0
        n=int(input())
        p1=1<=n<=10**5
        p2=n==1
        if not p1:continue
        for j in range(2,int(n**0.5)+1):
            if j==n:continue
            if n%j==0:
                p3=1
                break
        print('No'if p2+p3 else'Yes')
else:print('请满足1≦T≦10的正整数')

发表于 2025-10-29 11:23:57 回复(0)
C
牛客915416951号头像 牛客915416951号
#include <stdio.h>
int su(int c) {
    if (c <= 1) return 0;
    for (int i = 2; i < (c / 2) + 1; i++) {
        if (c % i == 0)
            return 0;    
}
    return 1;
}
int main() {
    int n, a;
    scanf("%d\n", &n);
    for (int i = n; i > 0; i--) {
        scanf("%d\n", &a);
        printf(su(a)?"Yes\n":"No\n");
    }
}
发表于 2025-09-27 20:26:30 回复(0)
C++
YSE0头像 YSE0
素数判断题解
适合新手 

#include <cmath>
#include <iostream>
using namespace std;
bool is_prime(int num){
    if(num<=1)return false;
    if(num==2)return true;
    if(num%2==0)return false;
    for(int i=3;i<=sqrt(num);i+=2){
        if(num%i==0)return false;
    }
    return true;
}//筛选素数
int main(){
    int T;
    cin>>T;
    for(int a=1;a<=T;a++){  //设定循环
    int n;
    cin>>n;
    if(is_prime(n)){cout<<"Yes"<<endl;}
    else{cout<<"No"<<endl;}//判断素数
    }
    return 0;
}

发表于 2025-09-15 23:07:47 回复(0)
Java
牛客200621362号头像 牛客200621362号 
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        for(int i = 1;i<=T;i++){
            int n = in.nextInt();
            if(prime(n)){
                System.out.println("Yes");
            }else{
                System.out.println("No");
            }
        }
    }

    public static boolean prime(int n){
        if(n <= 1) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false;

        //只检查从 3 到 √n 之间的所有奇数
        for(int j = 3;j*j <= n;j += 2){
            if(n%j == 0) return false;
        }
        return true;
        
    }
}

发表于 2025-08-13 16:23:13 回复(0)
Python3
木木E12头像 木木E12
import math

def isprime(n):
    if n == 1:
        return False
    for i in range(2, math.isqrt(n)+1, 1):
        if n % i == 0:
            return False
    return True

T = int(input())
for i in range(T):
    n = int(input())
    if isprime(n):
        print('Yes')
    else:
        print('No')
发表于 2025-08-13 16:18:21 回复(0)
C
WhitenineM头像 WhitenineM
#include <stdio.h>
int main() {
    int T, i, j, k;
    scanf("%d", &T);
    if (T <= 0)
        return 0;
    int array[T];
    for (i = 0; i < T; i++) {
        scanf("%d", &array[i]);
    }

    for (j = 0; j < T; j++) {
        int isPrime = 1;
        if (array[j] < 2)
            isPrime = 0;
        else {
            for (k = 2; k < array[j]; k++) {
                if (array[j] % k == 0) {
                    isPrime = 0;
                    break;
                }
            }
        }
        printf(isPrime ? "Yes\n" : "No\n");
    }
    return 0;
}

发表于 2025-07-24 20:17:55 回复(0)
C++
追风的羽汀头像 追风的羽汀 
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n ;
    for(int i=1;i<=n;i++){
        int a;
        cin >> a;
        if( a>1 && a%1==0 && a%a==0)
        {
            int u = 0;
            for(int i=2;i<=a-1;i++){
                if( a%i==0 ){
                    u=1;
                }
            }
            if(u==1){
                cout<<"No"<< endl;
            }else{
                cout<<"Yes"<<endl;
            }
            
        }
        else{
            cout<<"No"<< endl;
        }
    }

}
稍微有点麻烦，干出屎山了
发表于 2025-07-14 12:45:01 回复(1)
Python3
爱健身的牛油果很愤怒头像 爱健身的牛油果很愤怒
T = int(input())

for _ in range(T):
    n = int(input())
   
    if n<2:
        print('No')
        continue

    for i in range(2, int(n**0.5)+1):
        if n%i==0:
            print('No')
            break
    else:
        print('Yes')
发表于 2025-12-17 22:48:43 回复(0)
Python
爱吃的代码渣渣许愿简历通过头像 爱吃的代码渣渣许愿简历通过 

t = int(input())

while t > 0:
    a = int(input())
    s = 0
    for i in range(1, a + 1):
        if a % i == 0:
            s += 1
    if a > 1 and s == 2:
        print("Yes")
    else:
        print("No")
    t -= 1

发表于 2025-12-17 16:01:04 回复(0)
有担当的做题家在努力存钱头像 有担当的做题家在努力存钱
n = int(input())
for x in range(0,n):
   num = int(input())
   if num < 2:
      print("No")
   elif num == 2:
      print("Yes")
   else:
      is_prime = True
      for j in range(2, num):
         if num % j == 0:
            print("No")
            is_prime = False
            break
      if is_prime:
         print("Yes")

发表于 2025-12-09 20:09:19 回复(0)
C++
来吾告汝头像 来吾告汝 
#include <iostream>
using namespace std;
#include <cmath>

bool mydigit() {
    int num;
    cin >> num;
    if(num == 1){
        return false;
    }
    for (int j = 2; j <= sqrt(num); ++j) {
        if (num % j == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        if(mydigit()){
            cout << "Yes" << endl;
        }
        else{
            cout << "No" << endl;
        }
    }
}
// 64 位输出请用 printf("%lld")

发表于 2025-12-09 01:21:33 回复(0)
大便王头像 大便王
#include<bits/stdc++.h>
using namespace std;

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) {//实际上到根号n就行了，可以减少循环次数
        if (n % i == 0) return false; 
    }
    return true;  
}

void solve() {
    int n;
    cin >> n;
    cout << (isPrime(n) ? "Yes" : "No") << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

发表于 2025-12-02 17:44:50 回复(0)
C
oneFATcat头像 oneFATcat
#include<stdio.h>

int Judge(int x)
{
    if(x <= 1) return 0;
    if(x == 2) return 1;
    if(x % 2 == 0) return 0;
    for(int y = 3;y * y <= x;y += 2)
    {
        if(x % y == 0) return 0;
    }
    return 1;
}
int main()
{
    int T,n;
    scanf("%d",&T);
    for(int m = 1;m <= T;m++)
    {
        scanf("%d",&n);
        if(Judge(n))
        {
            printf("Yes\n");
        }
        else
        {
            printf("No\n");
        }
    }
    return 0;
}
发表于 2025-11-27 16:26:12 回复(0)
提交观点

问题信息

语言题 过关题目
上传者：牛客301599号
难度：
57条回答 1126浏览

热门推荐

相关试题

素数判断

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号