素数的求法

大家好，欢迎来到IT知识分享网。

一、素数的定义：

素数即为质数，一个数要是素数（质数）的话，需要满足下列的条件

（1）大于 1 的正整数；

（2）只能被 1 和自身整除；

（3）最小的素数是 2 。

二、问题描述

 输入一个值 n ，求出小于 n 值的所有素数

例子：

输入：20

输出：2  3  5  7  11  13  17  19 

三、问题解决 

思路1

试除法：将该数逐个和从 2 到 （n – 1）或者（n / 2）或者（n ^ 1/2） 的数相除，若都无法除尽，即为素数

（1） 逐个和从 2 到 n – 1 的数相除，若都无法除尽，即为素数

代码：

import java.util.Scanner; public class Prime { public static void main(String[] args) { //判断是否为素数的标志量（true不是素数，false是素数） boolean flag; System.out.print("请输入n:"); Scanner sc = new Scanner(System.in); int n = sc.nextInt(); //从2开始一直循环到 n - 1 for(int i = 2;i < n;i++) { flag=false; for(int j = 2;j <= i - 1;j++) { if(i % j == 0) { //如果有一个数除得尽则这个数就不是质数 flag=true; break; } } //所有的都除不尽后就是质数 所以输出 if(flag == false) { System.out.print(i + " "); } } } }

运行结果：

（2） 逐个和从 2 到 n / 2 的数相除，若都无法除尽，即为素数

代码：

import java.util.Scanner; public class Prime { public static void main(String[] args) { //判断是否为素数的标志量（true不是素数，false是素数） boolean flag; System.out.print("请输入n:"); Scanner sc = new Scanner(System.in); int n = sc.nextInt(); //从2开始一直循环到 n / 2 for(int i = 2;i < n;i++) { flag=false; for(int j = 2;j <= i / 2;j++) { if(i % j == 0) { //如果有一个数除得尽则这个数就不是质数 flag=true; break; } } //所有的都除不尽后就是质数 所以输出 if(flag == false) { System.out.print(i + " "); } } } }

运行结果：

 

（3） 逐个和从 2 到 n ^ 1/2 的数相除，若都无法除尽，即为素数

代码：

import java.util.Scanner; public class Prime { public static void main(String[] args) { //判断是否为素数的标志量（true不是素数，false是素数） boolean flag; System.out.print("请输入n:"); Scanner sc = new Scanner(System.in); int n = sc.nextInt(); //从2开始一直循环到 n ^ 1/2 for(int i = 2;i < n;i++) { flag=false; for(int j = 2;j *j <= i;j++) { if(i % j == 0) { //如果有一个数除得尽则这个数就不是质数 flag=true; break; } } //所有的都除不尽后就是质数 所以输出 if(flag == false) { System.out.print(i + " "); } } } }

运行结果：

 

思路2

筛选法：由于2是公认最小的质数，则先把所有2的倍数去掉；然后剩下的那些大于2的数里面，最小的是3，所以3也是质数；然后把所有3的倍数都去掉，剩下的那些大于3的数里面，最小的是5，所以5也是质数……上述过程不断重复，就可以把某个范围内的质数了。

代码：

import java.util.Scanner; public class Prime { public static void main(String[] args) { System.out.print("请输入n："); Scanner sc = new Scanner(System.in); int n = sc.nextInt(); sc.close(); System.out.println(); // 设所有数都是素数，当某个数是素数，则其值为0 int[] isPrime = new int[n]; // 0 和 1 不是素数 isPrime[0] = 1; isPrime[1] = 1; for(int i = 2; i * i < n ;i++) { // 从最小素数2开始 if(isPrime[i] == 0) { for(int j = i*i; j < n; j += i) { // 标识该位置为非素数 isPrime[j] = 1; } } } //array为0的都是素数 for(int i=0;i < n;++i) { if(isPrime[i] == 0) { System.out.print(i + " "); } } } } 

运行结果：