数学知识----质数

简介: 数学知识----质数

质数

质数是针对于大于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;
            }
        }
    }
}

每次循环,遍历一次素数,除去素数对应的倍数


相关文章
|
8月前
|
存储 算法
【动态规划专栏】专题一:斐波那契数列模型--------1.第N个泰波那契数
【动态规划专栏】专题一:斐波那契数列模型--------1.第N个泰波那契数
72 1
|
8月前
|
算法
【动态规划专栏】专题一:斐波那契数列模型--------3.最小花费爬楼梯
【动态规划专栏】专题一:斐波那契数列模型--------3.最小花费爬楼梯
61 2
|
8月前
|
人工智能 算法 BI
数学知识:质数与约数
数学知识:质数与约数
72 0
|
6月前
递推7------7-7 sdut-C语言实验-三国佚事——巴蜀之危分数
递推7------7-7 sdut-C语言实验-三国佚事——巴蜀之危分数
28 0
|
8月前
|
存储 索引
题目----LeeCode热题100--1 两数之和
题目----LeeCode热题100--1 两数之和
50 1
|
8月前
【每日一题Day170】LC1040移动石子直到连续 II | 双指针 贪心 数学
【每日一题Day170】LC1040移动石子直到连续 II | 双指针 贪心 数学
60 1
|
8月前
力扣每日一题 ---- 2906. 构造乘积矩阵
力扣每日一题 ---- 2906. 构造乘积矩阵
|
8月前
函数递归详解----跳台阶、斐波那契数列、汉诺塔问题
递归的思想:把⼀个⼤型复杂问题层层转化为⼀个与原问题相似,但规模较⼩的⼦问题来求解;直到⼦问题不能再被拆分,递归就结束了。所以递归的思考⽅式就是把⼤事化⼩的过程。递归中的递就是递推的意思,归就是回归的意思。
|
机器学习/深度学习 人工智能
数学知识-质数
数学知识-质数