素数判断

  public static boolean inPrime(long num) {
        for (int i = 2; i * i <= num; i++)//i^2 <=> sqrt
            if (num % i == 0) return false;
        return true;
    }

质因分解

任何整数质因数分解是唯一的

Map

import java.util.HashMap;
import java.util.Map;
public static Map<Integer, Integer> pirmeFactor(int num) {
        Map<Integer, Integer> map = new HashMap<>();//质因数，出现次数
        for (int i = 2; i * i <= num; i++) {
            while (num % i == 0) {
                Integer v = map.get(i);
                if (v == null)
                    map.put(i, 1);
                else
                    map.put(i, v + 1);
                num /= i;
            }
        }
        return map;
    }

测试及其遍历

public static void main(String[] args) {
        System.out.println(pirmeFactor(100));
        //遍历map
        Map<Integer,Integer> map=pirmeFactor(100);//质因数 出现的次数
        StringBuilder sb=new StringBuilder();
        for(Map.Entry<Integer,Integer> entry: map.entrySet()){
            int k=entry.getKey();
            int v=entry.getValue();
            for (int i = 0; i < v; i++) {
                sb.append("*"+k);
            }
        }
        System.out.println(sb.substring(1));//从第一个字符开始
    }

求第N个素数

求第N个素数 传统一个一个算的话就是 nqrt(n)
所以使用 埃氏筛法 来高效求得素数<=O(nlognlogn)

• 2的倍数 干掉
• 3的倍数干掉
• 4的倍数干掉....

素数定理

从不大于n的自然数随机选一个，它是素数的概率大约是1/ln n
言简意赅就是 2~n的正整数中 素数的概率是 1/ln(n) 那么个数范围 就是n/ln(n)

关于java log

double x = Math.log(5);
等价于：x = ln 5 或 x = loge5，即以e为底的自然对数。

假如你想使用Java来计算机对数，算底不同的对数又该如何做呢？很遗憾，我们还没有办法计算以10为底或以2为底的对数。但是它们却是在计算Java对数时用的最多的。要想解决这个问题，需要使用数学和对数方程：

logx(y) =loge(y) / loge(x)，换底公式

代码

import static java.lang.StrictMath.log;
/**
     * 求第N个素数
     *
     * @param N
     */
    public static void m1(int N) {
        //由素数定理：
        //从不大于n的自然数随机选一个，它是素数的概率大约是1/ln n
        //N是第N 个素数
        //已知在整数x内大概有 x* 1/ln (x)个素数
        //现在我们要逆推：要想求第N个素数，我们的整数范围是什么
        //n就是整数范围
        int n = 2;
        while (n / log(n) <= N) {
            n++;
        }
        //开辟数组，下标自然数，数值mark
        //筛选法 标记素数
        int arr[] = new int[n];
        int x = 2;
        while (x < n) {
            //标记过了 继续下一个
            if (arr[x] != 0) {
                x++;
                continue;
            }
            int k = 2;
            //对于每个x 我们从2倍开始，对x的k倍 都mark -1
            while (x * k < n) {
                arr[x * k] = -1;
                k++;
            }
            x++;
        }
        //筛完之后，这个很长的数组里面非素数下标对应的值都是-1
        int sum = 0;
        for (int i = 2; i < arr.length; i++) {
            //是素数 计数+1
            if (arr[i] == 0) {
                sum++;
            }
            if (sum == N) {//素数的计数
                System.out.println(i); //索引是数值
                return;
            }
        }
    }

GitHub

所以解得第100002个素数是1299743
突然让我想起 李志锐师傅 帮我在科创论坛www.kechuang.org注册 求第N个素数 找他帮我算，写了一大串代码qwq 哈哈

参考文献：