dabocaiqq 2020-03-25 17:16 采纳率: 63.1%
浏览 347
已采纳

高分悬赏:Java语言如何编写程序判断2的n次方-1是不是质数

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

  • 写回答

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次方之和的角度考虑)

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
  • piaoyiren 2020-03-25 17:38
    关注

    public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    System.out.print("请输入一个整数:");

    BigInteger num = sc.nextBigInteger();
    while(true) {
    BigInteger result=BigInteger.valueOf(1);
    for(BigInteger j=BigInteger.valueOf(2);j.compareTo(num)<=0;j=j.add(BigInteger.valueOf(1))) {
    result=result.multiply(BigInteger.valueOf(2));
    }
    result=result.multiply(num);
    result=result.subtract(BigInteger.valueOf(1));
    for(BigInteger j=BigInteger.valueOf(2);j.compareTo(result)<=0;j=j.add(BigInteger.valueOf(1))) {
    if(result.divide(j).equals(0)) {
    System.out.println("no");
    break;
    }
    if(result.subtract(BigInteger.valueOf(1)).compareTo(j) == 0) {
    System.out.println("yes");
    }

            }
            System.out.println(result);
            System.out.print("请输入一个整数:");
            num =  sc.nextBigInteger();
        }
    
    }
    不是我的程序不行,是你输入的数太大了,我输入24就有点慢了,输入8884根本就计算不出来
    
    评论
  • sanshizhang 2020-03-25 17:39
    关注

    package com.test;

    import java.util.Scanner;

    public class Test3 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
    
        System.out.println("请输入n值:");
        Scanner input = new Scanner(System.in);
        String str = input.next();
        System.out.println("输入的值是:"+str);
        System.out.println("是否是质数? 答案是:"+match2(Integer.valueOf(str)));
    }
    
    /**
     * 判断是否是质数
     * 
     * @param i
     * @return
     */
    private static boolean match2(int n) {
                Double d = Math.pow(2, n);
        n = d.intValue()-1;
        for (int i = 2; Math.sqrt(n) >= i; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
    

    }
    //控制台
    请输入n值:
    15
    输入的值是:15
    是否是质数? 答案是:false

    评论
  • WTIAW.TIAW 2020-03-25 18:40
    关注

    想要高效就用欧拉筛法 O(nloglogn)可以将数据提到1e7左右。

    评论
  • Italink 2020-03-26 08:44
    关注

    用C++写了一个
    如果n是质数,那么(2^n)-1必定是质数

    #include <iostream>
    using namespace std;
    bool isPrim(const int& num) {
        for (int i = 2; i <= sqrt(num); i++)
            if (num % i == 0)
                return false;
        return num>1;
    }
    int main() {
        int n;
        cin >> n;
        cout << (isPrim(n) ? "yes" : "no") << endl;
        return 0;
    }
    
    评论
查看更多回答(4条)

报告相同问题?

悬赏问题

  • ¥15 最小生成树问题 Prim算法和Kruskal算法
  • ¥25 医院住院病人呼叫器设计
  • ¥15 不想和现在的团队合作了,怎么避免他们对程序动手脚
  • ¥30 c++类和数组实验代码
  • ¥20 C语言字符串不区分大小写字典排序相关问题
  • ¥15 关于#python#的问题:我希望通过逆向技术爬取1688搜索页下滑加载的数据
  • ¥15 关于Linux的终端里,模拟实现一个带口令保护的屏保程序遇到的输入输出的问题!(语言-c语言)
  • ¥30 请问,这个嵌入式Linux系统怎么分析,crc检验区域在哪
  • ¥15 二分类改为多分类问题
  • ¥15 Unity微信小游戏上调用ReadPixels()方法报错