试除法判定质数

雨点打透心脏的1/2处 2024-03-31 13:02 84阅读 0赞

## 试除法判定质数 ##

题目：  
给定 n 个正整数 ai，判定每个数是否是质数。

输入格式  
第一行包含整数 n。

接下来 n 行，每行包含一个正整数 ai。

输出格式  
共 n 行，其中第 i 行输出第 i 个正整数 ai 是否为质数，是则输出 Yes，否则输出 No。

数据范围  
1≤n≤100,  
1≤ai≤231−1  
输入样例：  
2  
2  
6  
输出样例：  
Yes  
No

**提交代码**：

import java.util.*;
    
    public class Main
    {
        
        static int n;
        static int [] a = new int [110];
        public static void main(String[] args)
        {
        
            Scanner in = new Scanner (System.in);      
            n = in.nextInt();
            for (int i = 0; i < n; ++ i) a[i] = in.nextInt();
            for (int i = 0; i < n; ++ i)
            {
        
                if (isPrime(a[i])) System.out.println("Yes");
                else System.out.println("No");
            }
        }
        public static boolean isPrime(int x)
        {
        
            if (x < 2) return false;
            // 这里的 i <= n / i 的原理等于 i * i <= n 但是不推荐后者 
            // 因为后者可能i * i 最后结果超出int范围
            // 也不推荐 i <= sqrt(n) 因为 sqrt这个函数很慢
            for (int i = 2; i <= x / i; ++ i) if (x % i == 0) return false;
            return true;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，84人围观）

还没有评论，来说两句吧...

相关阅读

相关试除法求约数

试除法求约数给定 n 个正整数 ai，对于每个整数 ai，请你按照从小到大的顺序输出它的所有约数。输入格式第一行包含整数 n。接下来 n 行，每行包含一个

偏执的太偏执、/ 2024年03月31日 13:47/ 0 赞/ 67 阅读

相关试除法判定质数

试除法判定质数题目：给定 n 个正整数 ai，判定每个数是否是质数。输入格式第一行包含整数 n。接下来 n 行，每行包含一个正整数 ai。输出格

雨点打透心脏的1/2处/ 2024年03月31日 13:02/ 0 赞/ 85 阅读

相关试除法求约数：深入分析与实践

试除法求约数：深入分析与实践在数学和算法领域，约数，也称因数，是一个非常基础的概念。给定一个整数，它的所有约数是能够整除它的数。例如，6 的约数包括 1、2、3 和 6

矫情吗；*/ 2024年02月20日 08:50/ 0 赞/ 61 阅读

相关试除法判定质数：深入探索与代码分析

试除法判定质数：深入探索与代码分析质数它是只有 1 和其自身两个正因子的自然数，例如：2、3、5、7 等。这篇文章将探讨如何使用试除法来判定一个数字是否为质数，并通过提

「爱情、让人受尽委屈。」/ 2024年02月20日 08:49/ 0 赞/ 66 阅读

相关质数 AcWing 866. 试除法判定质数

质数 AcWing 866. 试除法判定质数原题链接 [AcWing 866. 试除法判定质数][AcWing 866.] 算法标签数学知识质数试除

雨点打透心脏的1/2处/ 2023年09月28日 11:33/ 0 赞/ 123 阅读

相关关于质数的判定与快速筛法

一. 关于质数： 1.质数和合数是针对所有大于1的 “自然数” 来定义的(所有小于等于1的数都不是质数). 2.所有小于等于1的整数既不是质数也不是合数. 3.质数和

男娘i/ 2023年09月24日 14:26/ 0 赞/ 63 阅读

相关试除法求数的约数

上一篇博客：[分解质因数][Link 1] > 写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。如果

一时失言乱红尘/ 2022年11月18日 01:26/ 0 赞/ 183 阅读

相关 JAVA质数的判定以及输出指定范围的质数

一. 编者按: 互联网上关于质数的Java代码数不胜数,本人刚进入Java世界,关于Java的代码皆为本人学习代码,供大家交流和参考,若有不足或者错误还请指正.QQ116

迷南。/ 2022年06月02日 06:37/ 0 赞/ 234 阅读

相关【算法】试除法求素数

判定一个数是否为素数(只能被1和本身整除)通常用小于这个数的所有数去试除他，看是否能被整除，显然不够简便。优化： 1. 除了2以外，其他偶数全都不为素数(能被2整除

心已赠人/ 2022年04月01日 03:12/ 0 赞/ 293 阅读

相关 C语言——质数判定

Description 质数被定义为一个不能除了1和它本身整除的正整数。你的任务就是要编写一个程序，判定任意一个大于等于2的正整数是否是质数。 Input 输入只有一

亦凉/ 2022年03月21日 03:15/ 0 赞/ 232 阅读