从键盘输入n，计算2的n次方-1是不是质数
如果是，输出yes，如果不是，输出no
比如输入：859433
输出yes
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次方之和的角度考虑）
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根本就计算不出来
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
想要高效就用欧拉筛法 O(nloglogn)可以将数据提到1e7左右。
用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;
}