寻找大素数算法

寻找大素数算法packageprimeNumber;importjava.util.Arrays;importjava.util.Scanner;/***本文系作者高中时候与同学讨论的结果生成结果是依据素数定理推倒而来依据此公式可以求出无限大的素数但非公理次计算结果虽然可以求无限大的素数但仍需验证**@author王伟2020-3-18**/publi…

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

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 + “”);
            }
        }
    }
}
 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/150327.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • p2p文件服务器,P2P文件传输

    p2p文件服务器,P2P文件传输>网络中的应用,存在两种主流的体系结构。一种是C-S体系,另一种是P2P(对等网)体系。#C-S体系C-S体系是应用很广泛的应用程序体系,如Web应用。在C-S体系中,服务器承担着巨大的责任,需要处理大量的客户端请求,如文件下载请求,这种体系之间**客户端不能直接通信**,而是通过服务器传达。#P2P体系P2P,即peer-to-peer,意思是对等网络。P2P区分于C-S的就是这种体…

  • 日志分析_周记10篇

    日志分析_周记10篇日志信息每个用例都会生成一个对应的log日志,位置:<ProjectRootDir>/logs/TestCaseID.run.log.如果你想看到request和response、提取

  • vim的复制粘贴命令_vim编辑器常用命令

    vim的复制粘贴命令_vim编辑器常用命令接触linux操作系统之后使用vi/vim编辑器用的就比较多,其实vi/vim编辑文件特别方便,但是一些常见的指令模式下的命令确很容易忘,特别是复制剪切粘贴经常忘,所以小结下以后查用起来比较方便。1.复制剪切粘贴撤销复制:复制一行则:yy复制三行则:3yy,即从当前光标+下两行。复制当前光标所在的位置到行尾:y$复制当前光标所在的位置到行首:y^剪切:剪切一行:dd前切三

  • Mac下 Vim删除多行快捷键

    Mac下 Vim删除多行快捷键Mac下,Vi和Vim是神一样的编辑器,如何删除多行。以下以编辑host文件为例首先在Terminal中,输入vim/etc/hosts,按return。进入vim的默认模式。Vim有三种模式命令模式,编辑模式,和默认模式按esc进入命令模式,可以使用退出,存盘退出,不存盘退出等命令。命令模式稍后整理按a进入编辑模式的ins

  • echarts图表在Tab页中width: 100%失效导致的第一个Tab页之后的Tab页图表不能正常显示的问题

    echarts图表在Tab页中width: 100%失效导致的第一个Tab页之后的Tab页图表不能正常显示的问题

    2021年11月22日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号