从键盘输入n,计算2的n次方-1是不是质数
如果是,输出yes,如果不是,输出no
比如输入:859433
输出yes

高分悬赏:Java语言如何编写程序判断2的n次方-1是不是质数
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
5条回答 默认 最新
- qybao 2020-03-26 18:47关注
2的n次方就是1<<n(1左移n位的二进制数),2的n次方减1的二进制位都是1,从中受到启发,貌似发现了一个规律
如果该二进制数的1的串刚好被分成相同长度的2个1以上的子串的组合,则该数不是质数,否则,该数是质数(即二进制数的1的串不能分成相同长度的2个1以上的子串的组合)
比如
2的2次方-1=3的二进制11(有2个1的串),不能分成2个1以上的子串的组合,所以是质数
2的3次方-1=7的二进制111(有3个1的串),不能分成2个1以上的子串的组合,所以是质数
2的4次方-1=15的二进制1111(有4个1的串),能分成2个1以上的子串的组合(即1111可由2组11组合),所以不是质数
2的5次方-1=31的二进制11111(有5个1的串),不能分成2个1以上的子串的组合,所以是质数
2的6次方-1=63的二进制111111(有6个1的串),能分成2个1以上的子串的组合(即111111可由2组111,3组11组合)
2的7次方-1=127的二进制1111111(有7个1的串),不能分成2个1以上的子串的组合,所以是质数
2的8次方-1=255的二进制11111111(有8个1的串),能分成2个1以上的子串的组合(即11111111可由2组1111,4组11组合)
2的9次方-1=511的二进制111111111(有9个1的串),能分成2个1以上的子串的组合(即111111111可由3组111组合)
2的10次方-1=1023的二进制1111111111(有10个1的串),能分成2个1以上的子串的组合(即1111111111可由5组11组合)
等等
所以变相的改成判断二进制数有几个1组成即可,即质数个1,也就是n是质数的时候,2的n次方-1也是质数,结果发现和LS说的规律一样
剩下还有什么规律还有待挖掘,不过上述的规律可以递归利用,或许在一定程度上可以优化一下public class Sample { public static void main(String[] args) { //Scanner sc = new Scanner(System.in); //int num = sc.nextInt(); int num = 859433; //int num = (1<<31)-1; long t1 = System.currentTimeMillis(); boolean b = isPNum(num); long t2 = System.currentTimeMillis(); System.out.println(t2-t1 + "=" + b); t1 = System.currentTimeMillis(); b = isPNum2(num); t2 = System.currentTimeMillis(); System.out.println(t2-t1 + "=" + b); } public static boolean isPNum(int num) { if (num==2) return true; else if (num<2 || num%2==0) return false; int tmp = num, n = 0; while (tmp>0) { //算出n n++; tmp >>= 1; } if (num==(1<<n)-1) { return isPNum(n); //利用规律递归,判断num是否符合2的n次方减1 } for (int i=3; i<=(1<<((n+1)/2)); i++) { //走到这里必然是奇数,所以for从3开始即可 if (num%i==0) return false; } return true; } public static boolean isPNum2(int num) { for (int i = 2; i <= Math.sqrt(num); i++) if (num % i == 0) return false; return num>1; } }
以后有时间再研究一下质数还有什么规律(比如从分解成2n次方之和的角度考虑)
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报
悬赏问题
- ¥15 最小生成树问题 Prim算法和Kruskal算法
- ¥25 医院住院病人呼叫器设计
- ¥15 不想和现在的团队合作了,怎么避免他们对程序动手脚
- ¥30 c++类和数组实验代码
- ¥20 C语言字符串不区分大小写字典排序相关问题
- ¥15 关于#python#的问题:我希望通过逆向技术爬取1688搜索页下滑加载的数据
- ¥15 关于Linux的终端里,模拟实现一个带口令保护的屏保程序遇到的输入输出的问题!(语言-c语言)
- ¥30 请问,这个嵌入式Linux系统怎么分析,crc检验区域在哪
- ¥15 二分类改为多分类问题
- ¥15 Unity微信小游戏上调用ReadPixels()方法报错