关于正整数、质数与公因数及哥德巴赫猜想

前言:

一个正整数可以分成若干组整数乘式:
若规定乘式左侧数小于右侧数,则所有乘数的集合便是该数的公因数。
如:24=1X24;24=2X12;24=3X8;24=4X6,则24的公因数是1,2,3,4,6,8,12,24
若将左乘数当做白球放于白盒,右乘数当做黑球放于黑盒,则
P1:每一个白球与一个黑球之间存在唯一连接,使两球积为[源数]24。

P2:对于任何一个正整数E,E=1XE成立,所以白盒与黑盒存在必然元素。
P3:√E是白盒与黑盒的分界线,
白盒中的任意元素:Ew≤√E
黑盒中的任意元素:Eb≥√E

基于P1和P3,在寻找E的公因数时,只需寻找白盒中的所有元素,便可推出黑盒中的元素。寻找区间缩小至[2,√E]
将黑白盒的元素去重后便可得到E的所有公因数集合。
根据该集合元素个数,可将正整数数分为:
(1)既不是质数也不是合数:元素个数1
(2)素数(质数):元素个数2
(3)合数:元素个数≥2
黑白盒.png

编程实现:

功能:1.得到一个数的所有公因数

2.判断一个数是否是素数(质数)

3.取到范围内的所有素数

4.给出一个数的哥德巴赫猜想的表达式

/**
 * 作者:张风捷特烈
 * 时间:2018/8/24 0024:8:21
 * 邮箱:1981462002@qq.com
 * 说明:正整数集合
 */
public class PInt {

    private List<Integer> whiteBox = new ArrayList<>();//白盒
    private List<Integer> blackBox = new ArrayList<>();//黑盒

    private int mNum;//传入数据

    public PInt(int num) {
        mNum = num;
        if (num <= 0) {
            new RuntimeException("It is can't small than Zero");
        }
    }

    /**
     * 收集所有公因数
     *
     * @return
     */
    public List<Integer> collectBall() {
        collectWhiteBall();
        collectBlackBall();
        LinkedHashSet<Integer> set = new LinkedHashSet<>();
        set.addAll(whiteBox);
        set.addAll(blackBox);
        return new ArrayList<>(set);
    }

    /**
     * 白盒收集公因数
     */
    private void collectWhiteBall() {
        whiteBox.add(1);
        double limitLine = Math.sqrt(mNum);//白盒边界最大值
        for (int i = 2; i <= limitLine; i++) {
            if (mNum % i == 0) {
                whiteBox.add(i);
            }
        }
    }

    /**
     * 用白盒映射出黑盒中公因数
     */
    private void collectBlackBall() {
        for (Integer i : whiteBox) {
            blackBox.add(mNum / i);
        }
    }

    /**
     * 判断是否是质数
     *
     * @return
     */
    public boolean isPrime() {
        return collectBall().size() == 2;
    }

    /**
     * 判断是否是质数
     *
     * @return
     */
    public static boolean isPrime(int num) {
        PInt pInt = new PInt(num);
        return pInt.collectBall().size() == 2;
    }

    /**
     * 获取区域内的所有质数(含起始)
     *
     * @param a 起始点
     * @param b 终止点
     * @return
     */
    public static ArrayList<Integer> getPrimeFromA2B(int a, int b) {

        ArrayList<Integer> list = new ArrayList<>();
        for (int i = a; i <= b; i++) {
            PInt pInt = new PInt(i);
            if (pInt.isPrime()) {
                list.add(i);
            }
        }
        return list;
    }

    /**
     * 一个数的哥德巴赫猜想所有可能表达式
     * @param num
     * @return
     */
    public static String guess(int num) {
        ArrayList<Integer> rightBox = new ArrayList<>();
        for (int i = 0; i <= num / 2; i++) {
            if (PInt.isPrime(i) && PInt.isPrime(num - i)) {
                rightBox.add(i);
            }
        }
        StringBuilder sb = new StringBuilder();
        for (Integer i : rightBox) {
            sb.append(i + "+" + (num - i) + "=" + num + "\n");
        }
        return sb.toString();
    }
}
测试类:公因数测试
public class Client {
    public static void main(String[] args) {
        PInt pInt = new PInt(510412736);
        System.out.println(pInt.collectBall());
        //[1, 2, 4, 8, 16, 32, 64, 510412736, 255206368
        //, 127603184, 63801592, 31900796, 15950398, 7975199]
    }
}
范围质数测试:10W数量级0.5s左右
public class Client {
    public static void main(String[] args) {
        long time = System.currentTimeMillis();
        System.out.println(PInt.getPrimeFromA2B(0, 100000));
        long time1 = System.currentTimeMillis();
        System.out.println("time:" + (time1 - time)/1000.f + "秒");
    }
}
范围质数测试
哥德巴赫猜想测试
public class Client {
    public static void main(String[] args) {
        System.out.println(PInt.guess(124));
    }
}
哥德巴赫猜想测试.png

本文由张风捷特烈原创,转载请注明

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

UOJ#386. 【UNR #3】鸽子固定器(链表)

如果我们按$s$排序后,我们就可以枚举$max  \ s_i$和$min \ s_i$

1101
来自专栏专注数据中心高性能网络技术研发

[LeetCode]Math主题系列{第7,9,13,273题}

1.内容介绍 本篇文章记录在leetcode中Math主题下面的题目和自己的思考以及优化过程,具体内容层次按照{题目,分析,初解,初解结果,优化解,优化解结果,...

3537
来自专栏Albert陈凯

数据结构与算法汇总

文章作者博客微信公共账号:hadoop123(微信号为:hadoop-123),分享hadoop技术内幕,hadoop最新技术进展,发布hadoop相关职位和求...

3715
来自专栏落影的专栏

程序员进阶之算法练习(三十)附基础教程

BAT常见的算法面试题解析:程序员算法基础——动态规划程序员算法基础——贪心算法工作闲暇也会有在线分享,算法基础教程-。

2513
来自专栏极客慕白的成长之路

C++上机考试试题解析

1.6K3
来自专栏程序员宝库

用 PHP 的方式实现的各类算法合集

项目地址: https://github.com/PuShaoWei/arithmetic-php About 如果说各种编程语言是程序员的招式,那么数据结构和...

4567
来自专栏绿巨人专栏

Modern Algebra 读书笔记

3595
来自专栏乐百川的学习频道

一个余数问题的思考

刚刚在贴吧上看到一个很简单的算法小问题,顺便看到了很多人不同的思路。我觉得很有意思,所以也来研究一下。 问题如下: 一筐鸡蛋: 1个1个拿,正好拿完。...

2079
来自专栏cs

Mathematica学习笔记

放假了,近来无事,就复习了一下mathematica相关知识点。已经玩了很多东西,不过大概还是很熟悉。 Mathematica(我简称mma),可以通过交互方...

5746
来自专栏CDA数据分析师

开工大吉:几个让你月薪3万+的excel神技能

来源:运营圈信息流广告 职场中经常会用到哪些函数? IF函数、SUMIF函数、VLOOKUP函数、SUMPRODUCT函数...... 小编总结了8个在工作中常...

3996

扫码关注云+社区

领取腾讯云代金券