寻找大素数算法

寻找大素数算法

全栈程序员-站长 • 2022年6月18日下午1:36 • 未分类 • 阅读 22

大家好，又见面了，我是你们的朋友全栈君。

package primeNumber;

import java.util.Arrays;
import java.util.Scanner;

/**
* 本文系作者高中时候与同学讨论的结果生成结果是依据素数定理推倒而来依据此公式可以求出无限大的素数但非公理次计算结果虽然可以求无限大的素数但仍需验证
*
*/
public class primeNumber {

   public static void main(String[] args) {

       // 调用方法输入阶乘范围(long 类型仅支持70以内的阶乘)
       Scanner scan = new Scanner(System.in);
       int num = Integer.parseInt(scan.next());
       int[] primeArray = primes(num);
       // long 类型仅能支持70以内的阶乘
       long p = 1;
       // 阶乘范围内的所有素数
       // i从1开始因为后面还需加减2的
       for (int i = 1; i < primeArray.length; i++) {

           p *= primeArray[i];
       }
       /*
       * 根据素数定理间隔log e (mun)一定会出现一个素数且当num的值越大概率随之增大(详询百度百科)
       * 所以p±2^n有非常大概率是素数(n正整数) 并且num数值越大存在的素数越多
       */
       for (int i = 0; i < 20; i++) {

           System.out.println(i);
           System.out.println(Math.round(p + Math.pow(2, i)));
           // 分解验证
           getPrimer(Math.round(p + Math.pow(2, i)));

}
}

   // 寻找小范围内所有素数
   public static int[] primes(int n) {

       if (n < 0) {

           throw new IllegalArgumentException(
                   “N must be a non negative integer.”);
       }
       if (n <= 1) {

           return new int[0];
       }
       int len = ((n & 1) == 1) ? (n >> 1) + 1 : n >> 1;
       boolean[] p = new boolean[len + 1];
       for (int k = 3, limit = (int) Math.sqrt(n); k <= limit; k += 2) {

           if (!p[(k + 1) >> 1]) {

               for (int j = (k * k + 1) >> 1; j <= len; j += k) {

                   p[j] = true;
               }
           }
       }
       int primeNums = 0;
       /* 获取精确的素数数量，以免开辟过大的数组造成空间不足的情况。 */
       for (int i = 1; i <= len; i++) {

           if (!p[i]) {

               primeNums++;
           }
       }
       int[] primeArray = new int[primeNums];
       primeArray[0] = 2;
       int count = 1;
       for (int i = 2; i <= len; i++) {

           if (!p[i]) {

               primeArray[count++] = i * 2 – 1;
           }
       }
       return Arrays.copyOf(primeArray, count);
   }

   // 分解大数的质数因子验证
   public static void getPrimer(long num) {

       for (int i = 2; i <= num; i++) {

           if (num % i == 0) {

               System.out.print(i + ” “);
               getPrimer(num / i);
               break;
           }
           if (i == num) {

               System.out.print(i + “”);
           }
       }
   }
}