package zj.hy.love;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
/**
* 在‘e’的数列中所能找到的第一个十位数质数
* @author ZJ
* @since 2017-1-3
*/
public class Ques20170103_02 {
private static final BigInteger two = new BigInteger("2");
private static final BigInteger one = new BigInteger("1");
private static final BigInteger zero = new BigInteger("0");
private static final BigInteger oppositeOne = new BigInteger("-1");
/**
* 自然数e = 1/0!+1/1!+1/2!+....+1/(n-1)!+1/n! n=defaultCircle
* 当defaultCircle值越大模拟的自然数e越接近真实值
*/
private static final int defaultCircle = 1000000;
/**
* 存放一百以内的全部质数
*/
private static final List<BigInteger> primeList = new ArrayList<BigInteger>();
static{
// 一百以内的全部素数
int[] prime = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
for (int i = 0; i < prime.length; i++) {
primeList.add(new BigInteger(prime[i]+""));
}
}
/**
* 在任意数字型序列中寻找第一个bit位的质数<br>
* 数字型序列如:46165/1234.8974
* @param array 数字数列
* @param bit 截取字符串的长度
* @return 不存在时返回-1,存在则返回改质数
*/
public BigInteger findTenPrimeOfArray(String array,int bit){
if(array.contains(".")){
String[] a = array.split("\\.");
if(a[0].length()>=bit){
return getFirstTenPrime(a[0],bit);
}
if(a[1].length()>=bit){
return getFirstTenPrime(a[1],bit);
}
}else{
if(array.length()>=bit){
return getFirstTenPrime(array,bit);
}
}
return oppositeOne;
}
/**
* 从左到右依次截取字符串的bit位转换为数字,<br>
* 判断这个数字是否为质数,若是则返回改数字,若不存在返回-1
* @param array 数字型字符串
* @return
*/
private BigInteger getFirstTenPrime(String array,int bit){
int len = array.length();
int i = 0;
BigInteger temp;
boolean flag;
while(i<len-1-bit){
temp = new BigInteger(array.substring(0+i, bit+i));
flag = judgeNumberIsPrime(temp);
if(flag){
return temp;
}
i++;
}
return oppositeOne;
}
/**
* 测试一个数是否为质数<br>
* @param num
* @return
*/
public boolean judgeNumberIsPrime(BigInteger num){
if(num.compareTo(two)==-1){
return false;
}
int size = primeList.size();
for (int i = 0; i < size; i++) {
BigInteger res = montgomery(primeList.get(i),num.subtract(one),num);
if(!res.equals(one)&&!res.equals(zero)){
return false;
}
}
return true;
}
/**
* 蒙哥马利算法
* @param a 底数
* @param b 指数
* @param m 模数
* @return
*/
public BigInteger montgomery(BigInteger n,BigInteger p,BigInteger m){
BigInteger r = n.mod(m);
BigInteger tmp = one;
while(p.compareTo(one)==1){
if(!p.mod(two).equals(zero)){
tmp = tmp.multiply(r).mod(m);
}
r = r.multiply(r).mod(m);
p = p.divide(two);
}
return r.multiply(tmp).mod(m);
}
/**
* 获取自然数e
* @param scale 精度
* @return
*/
public static BigDecimal getNaturalConstant(int scale){
BigDecimal e = new BigDecimal(0);
BigDecimal t = new BigDecimal(1);
for (int i = 1; i < defaultCircle; i++) {
t = t.divide(new BigDecimal(i), scale, BigDecimal.ROUND_HALF_UP);
e = e.add(t);
}
return e;
}
//测试在‘e’的数列中所能找到的第一个十位数质数
public static void main(String[] args) {
Ques20170103_02 ques = new Ques20170103_02();
final int step = 1000;
for (int i = 1; i < 1000; i++) {
String e = getNaturalConstant(step*i).toString();//获取自然数小数点后1000位
String res = ques.findTenPrimeOfArray(e, 10).toString();
if(!oppositeOne.equals(res)){
System.out.println(res);
break;
}
}
}
}
分享到:
相关推荐
C语言程序设计-求一个n位自然数的各位数字的积;(n 是小于10的自然数).c
会自动截取收到的某特定号码的短信中的第一串数字,一般验证短信中验证码就是其中的第一串数字…… 代码写得比较随意,不过注释挺全的。涉及到循环性多线程控制,多线程更改主线程UI,广播拦截短信,正则表达式等...
var num1 = prompt('请输入第一个数:'); var re = prompt('请输入你要进行的运算符:'); var num2 = prompt('请输入第二个数:'); function getSum(num1,re,num2,) { switch (re) { case '+': return num1 + ...
【问题描述】 实现任意多位的两个大整数的加、减、乘运算。 【输入形式】 用文件“算式.txt”(与编译后的程序在同一目录下)输入两个十进制大整数A和B。 在文件“算式.txt”中依次分行输入以下内容:...
1. 第一行是超长正整数A; 2. 第二行是超长正整数B; 【输出形式】 输出只有一行,是长整数A减去长整数B的运算结果,从高到低依次输出各位数字。要求:若结果为0,则只输出一个0;否则输出的结果的最高位不能为0,...
任意一个四位数,只要他们各个位置上的数字不全相同,就有这样的规律:(1)将组成这个四位数的四个数由大到小排列,形成由这四个数字构成的最大的四位数;(2)将组成这个四位数的四个数由小到大排列,形成由这四个...
给定n 位正整数a,去掉其中任意k≤n 个数字后,剩下的数字按原次序排列组成一个 新的正整数。对于给定的n位正整数a 和正整数k,设计一个算法找出剩下数字组成的新数 最小的删数方案。 «编程任务: 对于给定的正...
用户输入一个三位自然数计算输出个十百位数字.py
一个素数,当她的数字位置对换以后仍为素数,这样的数称为绝对素数。
1.第一行是超长正整数A; 2.第二行是超长正整数B; [输出形式] 输出只有一行,是长整数A减去长整数B的运算结果,从高到低依次输出各位数字。要求:若结果为0,则只输出一个0;否则输出的结果的最高位不能为0,并且各位...
1.第一行是超长正整数A; 2.第二行是超长正整数B; [输出形式] 输出只有一行,是长整数A减去长整数B的运算结果,从高到低依次输出各位数字。要求:若结果为0,则只输出一个0;否则输出的结果的最高位不能为0,并且各位...
C语言编一个程序完成64位数据(无符号)的加法,减法运算
1、本程序实现计算任意长的整数的加、减法运算. 以用户和计算机对话的方式,即在计算机终端上显示“提示信息”之后,由用户在键盘上输入演示程序中规定的运算命令,然后程序就计算并显示出这两个数的运算。 2、本...
不用零食变量交换两个数字,简单明了,节省内存空间
选择该数据结构来完成长整数的加减运算是因为要对长整数进行运算,需要对长整数进行存储,所以选择用链表对长整数存储,又由于存储的顺序是从左到右,而运算的顺序则是从右到左,这样位了操作方便选择循环链表,在...
示例 1:输入:n = 3输出:3示例 2:输入:n = 11输出:0//确定 n 在几位数中第多个少位置上//根据 digit 得出几位数,及在几位数中的所处
(1) 实现int单参数构造函数,从int构造,允许隐式转换; (2) 实现const char *单参数构造函数,从十进制数字字符串构造,不允许隐式转换; (3) 实现拷贝构造函数和赋值操作符; (4) 实现整数类之间的加、减...
有效数字运算及分析方法偏差汇总2010版
用xilinx设计,仿真已经通过,4位ALU运算器。