素数判断
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;
}
}
}
所以解得第100002个素数是1299743
突然让我想起 李志锐师傅 帮我在科创论坛www.kechuang.org注册 求第N个素数 找他帮我算,写了一大串代码qwq 哈哈
参考文献:
本文地址:https://dxoca.cn/Algorithm/199.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。