判断质数

• • • 一、质数定义
    • 二、例题
    • • • （1）试题
        • （2）资源限制
        • （3）问题描述
        • （4）输入格式
        • （5）输出格式
        • （6）样例输入
        • （7）样例输出
    • 三、质数判定方法：试除法
    • • • （1）时间复杂度较高的暴力算法O(n)
        • • ①代码
          • ②评测结果
        • （2）时间复杂度较低的算法O(√n)
        • • ①代码
          • ②评测结果
    • 四、相关例题
    • • • （1）算法提高 质数1
        • • ①问题描述
          • ②输入格式
          • ③输出格式
          • ④样例输入
          • ⑤样例输出
          • ⑥代码
        • （2）算法提高 质数2
        • • ①问题描述
          • ②输入格式
          • ③输出格式
          • ④样例输入
          • ⑤样例输出
          • ⑥代码
        • （3）算法提高 素数之和
        • • ①问题描述
          • ②输入格式
          • ③输出格式
          • ④样例输入
          • ⑤样例输出
          • ⑥代码

一、质数定义

• 在大于1的整数中，如果只包含1和本身这两个约数，就被称为质数，或者叫素数

二、例题

（1）试题

• 算法提高 质数

（2）资源限制

• 内存限制：256.0MB
• C/C++时间限制：1.0s
• Java时间限制：3.0s
• Python时间限制：5.0s

（3）问题描述

• 输入一个数判断是否为质数。是则输出“yes”，否者输出“no”

（4）输入格式

• 一行一个正整数。

（5）输出格式

• 一行，“yes”或者“no”，意义见题面。

（6）样例输入

3

（7）样例输出

yes

三、质数判定方法：试除法

（1）时间复杂度较高的暴力算法O(n)

直接利用定义，从2到n-1每个都试除一下即可

①代码

import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();boolean result = is_prime(n);if (result == true){System.out.println("yes");}else {System.out.println("no");}}//判断质数//质数定义：在大于1的整数中，如果只包含1和本身这两个约数，就被称为质数，或者叫素数public static boolean is_prime(int n){if (n < 2){return false;}for (int i = 2; i < n; i++) {if (n % i == 0){return false;}}return true;}
}

②评测结果

（2）时间复杂度较低的算法O(√n)

被除数的两个约数总是对应存在的

• 例如：
  12的约数有3和4
  12/3 = 4
  12/4 = 3
• 假设：
  d是n的一个约数
  则n/d也是n的一个约束
  d<=n/d
  d的平方<=n
  d<=√n

因此我们所枚举的约数只需要到n/d就好了，大大降低了时间复杂度，降到了O(√n)

①代码

import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();boolean result = is_prime(n);if (result == true){System.out.println("yes");}else {System.out.println("no");}}//判断质数//质数定义：在大于1的整数中，如果只包含1和本身这两个约数，就被称为质数，或者叫素数public static boolean is_prime(int n){if (n < 2){return false;}for (int i = 2; i <= n/i; i++) {if (n % i == 0){return false;}}return true;}
}

②评测结果

四、相关例题

（1）算法提高 质数1

①问题描述

• 给定一个正整数N，请你输出N以内（不包含N）的质数以及质数的个数

②输入格式

• 输入一行，包含一个正整数N

③输出格式

• 共两行。
• 第1行包含若干个素数，每两个素数之间用一个空格隔开，素数从小到大输出。
• 第2行包含一个整数，表示N以内质数的个数。

④样例输入

10

⑤样例输出

2 3 5 7
4

⑥代码

import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int count = 0;if (n <= 2){System.out.println(0);}else {for (int i = 2; i < n; i++) {if (is_prime(i)){System.out.print(i+" ");count++;}}System.out.println();System.out.print(count);}}//判断质数//质数定义：在大于1的整数中，如果只包含1和本身这两个约数，就被称为质数，或者叫素数public static boolean is_prime(int n){if (n < 2){return false;}for (int i = 2; i <= n/i; i++) {if (n % i == 0){return false;}}return true;}
}

（2）算法提高 质数2

①问题描述

• 给定一个正整数N，请你输出N以内（不包含N）的质数以及质数的个数。

②输入格式

• 输入一行，包含一个正整数N

③输出格式

• 共两行。
• 第1行包含一个整数，表示N以内质数的个数。
• 第2行包含若干个素数，每两个素数之间用一个空格隔开，素数从小到大输出。

④样例输入

10

⑤样例输出

4
2 3 5 7

⑥代码

import java.util.ArrayList;
import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int count = 0;ArrayList l = new ArrayList<>();if (n <= 2){System.out.println(0);}else {for (int i = 2; i < n; i++) {if (is_prime(i)){l.add(i);count++;}}System.out.println(count);for (int i = 0; i < l.size(); i++) {System.out.print(l.get(i)+" ");}}}//判断质数//质数定义：在大于1的整数中，如果只包含1和本身这两个约数，就被称为质数，或者叫素数public static boolean is_prime(int n){if (n < 2){return false;}for (int i = 2; i <= n/i; i++) {if (n % i == 0){return false;}}return true;}
}

（3）算法提高 素数之和

①问题描述

• 给定正整数N,求[1,N]之间的所有素数之和.如果没有素数,则之和为0. 1<=N<=1000

②输入格式

• 输入有多行,每行有一个正整数n(1<=n<=1000),如果输入为0,则退出

③输出格式

• 对应每行输入的整数,输出[1,N]之间的所有素数之和.每个结果占一行.

④样例输入

1
2
4
0

⑤样例输出

0
2
5

⑥代码

import java.util.ArrayList;
import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);ArrayList a = new ArrayList();while (true){int n = sc.nextInt();if (n != 0){int sum = 0;if (n <= 1){a.add(0);continue;}else {for (int i = 2; i <= n; i++) {if (is_prime(i)) {sum += i;}}a.add(sum);continue;}}for (int i = 0; i < a.size(); i++) {System.out.println(a.get(i));}}}//判断质数//质数定义：在大于1的整数中，如果只包含1和本身这两个约数，就被称为质数，或者叫素数public static boolean is_prime(int n){if (n < 2){return false;}for (int i = 2; i <= n/i; i++) {if (n % i == 0){return false;}}return true;}
}