首页 > 试题广场 >

素数判断

[编程题]素数判断
  • 热度指数：60153 时间限制：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。
算法知识视频讲解
添加回答
C
牛客828449281号头像 牛客828449281号 
#include <stdio.h>
#define N 100001
char arr[N];
char* str[]={"Yes","No"};
int main() {
    arr[1]=1;
    for(int i=2;i<N;i++){
        if(arr[i]==0)for(int j=i+i;j<N;j+=i) arr[j]=1;
    }
    int n;
    scanf("%d",&n);
    while(scanf("%d",&n)!=EOF) printf("%s\n",str[arr[n]]);
    return 0;
}


发表于 2026-02-06 15:44:36 回复(0)
C
牛客423954602号头像 牛客423954602号
#include <stdio.h>
int main (){
int T;
int n=0;
scanf("%d",&T);
while(T--){
    scanf("%d",&n);
    int is_sushu=1;
    if(n<=1){
        is_sushu=0;
    }else if(n==2){
        is_sushu=1;
    }else{
        for(int a=2;a<=n;a++){
            if(a!=n&&n%a==0){
                is_sushu=0;
            }
        }
    }
    if(is_sushu==1){
        printf("Yes\n");
    }else if(is_sushu==0){
        printf("No\n");
    }
}
    return 0;
}
发表于 2026-02-06 09:56:41 回复(0)
C
牛客635731373号头像 牛客635731373号
#include <stdio.h>
#include <math.h>
int main() {
    int num;
    int i = 1;
    if(num <= 1){
        i = 0;
    }
    else if(num == 2){
        i = 1;
    }
    else if(num % 2 == 0){
        i = 0;
    }
    else{
        for(int x = 3 ; x*x <= num ; x += 2){
            if(num % x == 0){
                i = 0;
                break;
            }
        }
    }
    if (i){
        printf("Yes\n");
    }
    else{
        printf("No\n");
    }
    return 0;
}佬，麻烦看看这个代码哪里错了
发表于 2026-01-08 13:53:46 回复(1)
C
L1LL头像 L1LL 
#include <stdio.h>
#include <math.h>

int main() {
	int T;
	if (scanf("%d", &T) != 1) {
		return 1;
	}
	for (int i = 0; i < T; i += 1) {
		int n;
		if (scanf("%d", &n) != 1) {
			return 1;
		}
        if (n == 1) {
            printf("No\n");
            continue;
        }
		int m = sqrt(n), r = 0;
		for (int j = 2; j <= m; j += 1) {
			if (n % j == 0) {
				r = 1;
				break;
			}
		}
		printf("%s\n", r ? "No" : "Yes");
	}
	return 0;
}

发表于 2026-01-06 18:12:54 回复(0)
C
示申one头像 示申one
#include<stdio.h>
#include<stdlib.h>
void fun(int n){
    int j=0;
    for(int i=1;i<n;i++){
        if(n%i==0){
            j++;
        }
    }
    if(j==1){
        printf("Yes\n");
    }else {
    printf("No\n");
    }
}
int main(){
    int t,n;
    scanf("%d",&t);
    for(int i=0;i<t;i++){
scanf("%d",&n);
fun(n);
    }
    return 0;
}
发表于 2026-01-04 19:12:17 回复(0)
C
杨磊c头像 杨磊c
#include <stdio.h>

int main()
{
    int t;
    scanf("%d", &t);
    while (t--) 
    {
        int a;
        scanf("%d", &a);
        if (a == 1) 
        {
            printf("No\n");
            
        }
        if (a == 2) 
        {
            printf("Yes\n");
            
        }
        for (int i = 2; i < a; i++) 
        {
            if (a % i == 0) 
            {
                printf("No\n");
                break;    
            }
            else if(a-1==i)
            {
                printf("Yes\n");
            }
        }
        
    }

发表于 2025-12-27 16:49:56 回复(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
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)
C
DeepNick头像 DeepNick
#include <stdio.h>
int check(int a) {
    if (a<=1) return  0;
    if (a==2) return  1;
    if (a%2==0) return  0;
    for (int i=3;i<a/2;i++) {
        if (a%i==0) return  0;
    }
    return  1;

}
int main(){
int T;
    scanf("%d",&T);
    while (T--) {
        int n;
        scanf("%d",&n);

        if (check(n)) printf("Yes\n");
        else printf("No\n");

    }
    return  0;

}
发表于 2025-11-10 23:24:07 回复(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
Omnitrix_t头像 Omnitrix_t

还是用函数来写比较爽。

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

bool is_prime(int num)
{
    bool prime_falg = true;

    if (num <= 1)
    {
        return false;
    }

    for (int count = 2; count <= (int)sqrtf(num); count++)
    {
        if (num % count == 0)
        {
            prime_falg = false;
            break;
        }
    }

    return prime_falg;
}

int main() {

    int T = 0, n = 0;

    scanf("%d", &T);

    while (T--)
    {
        scanf("%d", &n);
        printf("%s\n", is_prime(n) ? "Yes" : "No");
    }

    return 0;
}
发表于 2025-08-06 20:30:04 回复(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)
提交观点

问题信息

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

热门推荐

相关试题

素数判断

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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