质数
质数是针对于大于1的自然数定义的，小于等于1的数既不是质数也不是合数
质数：
在大于1的整数中，如果只包含1和本身这两个约数，就被称为质数，或者叫素数
试除法判定质数
朴素做法：
package luogu.数学知识.质数; import java.util.Scanner; public class 质数的判定_试除法 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); System.out.println( is_prime(n) ); } 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; } }
优化：
package luogu.数学知识.质数; import java.util.Scanner; public class 质数的判定_试除法 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); System.out.println( is_prime(n) ); } static boolean is_prime( int n ) { if ( n<2 ) return false; //不写成 i*i<=n 如果i过大，那么会存在溢出的可能 //也不写成sqrt 速度较慢 for ( int i=2; i<=n/i; i++ ) { if ( n%i==0 ) return false; } return true; } }
分解质因数
package luogu.数学知识.质数; import java.util.Scanner; public class 分解质因数 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); divide(n); } static void divide( int n ) { for ( int i=2; i<=n; i++ ) { if ( n%i==0 ) { int s = 0; while ( n%i==0 ) { n /= i; s++; } System.out.println(i+" "+s); } } } }
优化：
n中最多只有一个大于sqrt(n)的质因子，因为如果有两个相乘会大于n
package luogu.数学知识.质数; import java.util.Scanner; public class 分解质因数 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); divide(n); } static void divide( int n ) { for ( int i=2; i<=n/i; i++ ) { if ( n%i==0 ) { //i一定为质数 //不为质数的数为某个质数的倍数，该个质数已经被除完 int s = 0; while ( n%i==0 ) { n /= i; s++; } System.out.println(i+" "+s); } } if ( n>1 ) System.out.println(n+" "+1); } }
筛素数
一个数不是质数，这个数的倍数也不为质数
一个数为质数，这个数的倍数不为质数
package luogu.数学知识.质数; import java.util.ArrayList; import java.util.Scanner; public class 筛素数 { static ArrayList<Integer> prime = new ArrayList<>(); static boolean[] nums = null; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); nums = new boolean[n+1]; getPrime(n); System.out.println(prime.toString()); } static void getPrime( int n ) { for ( int i=2; i<=n; i++ ) { //为素数 //去除素数的倍数 if ( !nums[i] ) { prime.add(i); } //去除倍数 for ( int j=i+i; j<=n; j+=i ) { nums[j] = true; } } } }
优化–埃氏筛法
package luogu.数学知识.质数; import java.util.ArrayList; import java.util.Scanner; public class 筛素数 { static ArrayList<Integer> prime = new ArrayList<>(); static boolean[] nums = null; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); nums = new boolean[n+1]; getPrime(n); System.out.println(prime.toString()); } static void getPrime( int n ) { for ( int i=2; i<=n; i++ ) { //为素数 //去除素数的倍数 if ( !nums[i] ) { prime.add(i); //去除倍数 for ( int j=i+i; j<=n; j+=i ) { nums[j] = true; } } } } }
线性筛法
package luogu.数学知识.质数; import java.util.ArrayList; import java.util.Scanner; public class 筛素数 { static ArrayList<Integer> prime = new ArrayList<>(); static boolean[] nums = null; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); nums = new boolean[n+1]; getPrime(n); System.out.println(prime.toString()); } static void getPrime( int n ) { for ( int i=2; i<=n; i++ ) { //为素数 //去除素数的倍数 if ( !nums[i] ) { prime.add(i); } for ( int j=0; prime.get(j)<=n/i; j++ ) { nums[prime.get(j)*i] = true; if ( i%prime.get(j)==0 ) break; } } } }
每次循环，遍历一次素数，除去素数对应的倍数
