`
u012081441
  • 浏览: 16036 次
  • 性别: Icon_minigender_1
  • 来自: 西安
社区版块
存档分类
最新评论

关于素数的简单算法整理

阅读更多
1、梅森尼数
import java.util.ArrayList;

public class text6 {

    /**
     * 梅森尼数(2的N次方减一是素数,N也必须是素数)
     */
    private static ArrayList<Integer> list = new ArrayList<Integer>();
    private static ArrayList<Integer> list1 = new ArrayList<Integer>();

    public static void main(String[] args) {
        // 求出(2的30次方的所有情况)
        fun();
        fun2();
        System.out.println("2的30次方以内的所有情况:");
        show();
    }

    // 求出1~30所有的素数并存放在list里面
    public static void fun() {
        for (int i = 1; i < 30; i++) {
            if (fun1(i)) {
                list.add(i);
            }
        }
    }

    // 判断数字是否素数
    public static boolean fun1(int k) {
        int i;
        for (i = 2; i < k; i++) {
            if (k % i == 0) {
                return false;
            }
        }
        if (i == k) {
            return true;
        }
        return false;
    }

    // 按照题目要求求出所有的梅森尼数保存在list1中
    public static void fun2() {
        for (int i = 0; i < list.size(); i++) {
            if (fun1((int) (Math.pow(2, list.get(i)) - 1))) {
                list1.add(list.get(i));
            }
        }
    }

    // 按照题目要求打印
    public static void show() {
        for (int i = 0; i < list1.size(); i++) {
            // int sum=(int) (Math.pow(2, list1.get(i))-1);
            System.out.println("2^" + list1.get(i) + "-1="
                    + (int) (Math.pow(2, list1.get(i)) - 1));
        }
    }

}

2、哥德巴赫猜想(任何大于2的偶数都能表示为两个素数之和)

package com.fit.getPingyin;

import java.util.ArrayList;

public class text8 {

    /**
     * 等差素数数列
     */
    private static ArrayList<Integer> list = new ArrayList<Integer>();

    public static void main(String[] args) {
        fun();
        System.out.println("100以内所有的等差素数数列:");// 最多只能解决100以内,其他不敢保证,存在问题
        fun2();

    }

    // 求出1~100所有的素数并存放在list里面
    public static void fun() {
        for (int i = 1; i < 100; i++) {
            if (fun1(i)) {
                list.add(i);
            }
        }
    }

    // 判断数字是否素数
    public static boolean fun1(int k) {
        int i;
        for (i = 2; i < k; i++) {
            if (k % i == 0) {
                return false;
            }
        }
        if (i == k) {
            return true;
        }
        return false;
    }

    // 根据条件求出所有的等差素数数列(还需要改进,存在漏洞)
    public static void fun2() {
        for (int i = 0; i < list.size(); i++) {
            for (int j = 0; j < list.size(); j++) {
                for (int k = 2; k < list.size(); k++) {
                    if (list.get(i) - list.get(j) == list.get(j) - list.get(k)
                            && list.get(i) != list.get(j)) {
                        System.out.print(list.get(i) + "," + list.get(j) + ","
                                + list.get(k) + " ");
                        if (list.get(i) - list.get(j) < 0) {
                            System.out.println("公差为:"
                                    + (-(list.get(i) - list.get(j))));
                        } else {
                            System.out.println("公差为:"
                                    + (list.get(i) - list.get(j)));
                        }
                    }
                }
            }
        }
    }
}

3.第100002个素数

public class text1 {

    /**
     * 第100002个素数
     */
    public static void main(String[] args) {
        int arr[] = new int[1500000];
        int n = 1;
        for (int i = 2; i < 1500000; i++) {
            for (int j = i * 2; j < 1500000; j = j + i) {
                arr[j] = 1;
            }
        }
        for (int i = 2; i <= 100002; i++) {
            while (arr[n = n + 2] == 1)
                ;
        }
        System.out.println(n);
    }

}
分享到:
评论

相关推荐

    大一萌新算法学习整理.pdf

    这是一份关于算法学习的整理文档,涵盖了多个重要的算法和数据结构相关的知识点。下面是对该文档的详细解读和知识点总结。 高精度运算 高精度运算是指在计算机科学中对大整数或高精度小数进行运算的方法。文档中...

    ACM算法模板2 算法整理

    6. **筛法求素数**:埃拉托斯特尼筛法是一种找出所有小于给定数n的素数的算法。它通过逐步剔除每个素数的倍数,最终留下的是素数。时间复杂度约为O(n log log n)。 7. **Splay**:Splay树是一种自调整的二叉查找树...

    Pascal基本算法整理

    以上就是关于Pascal语言中一些基本算法的介绍,包括数论算法(最大公约数、最小公倍数、素数判定)、最小生成树算法(Prim算法与Kruskal算法),以及DFS的基本实现。这些算法在实际编程中具有广泛的应用价值。

    全国计算机二级C常见算法整理.pdf

    1. 计数、求和、求阶乘等简单算法: 这类问题通常涉及到循环结构。例如,计算1到100范围内能被2或3整除的数之和,可以通过for循环遍历这个范围,每次检查当前数值是否满足条件,若满足则累加到总和中。求阶乘则需要...

    算法竞赛入门基础篇(个人整理)

    ### 算法竞赛入门基础篇(个人整理) #### 一、常用函数及算法 **1. 进制转换** - **十进制转R进制(2)** ```cpp string DtoR(int n, int r){ string s = ""; int x; if(n == 0){ s = "0"; } while(n){ ...

    c语言常用代码(简单算法)

    - 使用质数性质:一个大于1的整数如果不能被小于它的平方根的任何正整数整除,则它是素数。 - 通过循环遍历从2到该数的平方根的所有整数,检查是否有因数存在。 ### 五、6的倍数表示问题 #### 示例代码分析 ```...

    算法设计大报告题目.docx

    ### 知识点总结 #### 1. 欧几里得算法 ...以上是根据给定文件中的内容整理出来的核心知识点,涵盖了算法设计、实验操作、报告撰写等方面的内容。希望这些信息能帮助你更好地理解和完成相关的大作业要求。

    ACM/ICPC常用算法的代码库(吉林大学版,强烈推荐)

    这份文档提供了由吉林大学计算机科学与技术学院整理的一套针对ACM/ICPC竞赛的算法代码库。它包含了多种算法及其实现方式,适用于ACM/ICPC参赛者的学习和参考。这份代码库不仅涵盖了图论、网络流、数据结构等核心领域...

    简单数论及算法选讲 上海交大教练的资料

    总的来说,上海交通大学的这份《简单数论及算法选讲》资料是对数论知识的一个系统性整理,覆盖了数论的基础知识点以及一些关键算法。对于想要进入算法竞赛或者对数论感兴趣的初学者来说,这份资料无疑是一份宝贵的...

    经典算法大全,应该是c语言的

    从给定的文件标题“经典算法大全,应该是c语言的”和描述“经典算法大全,属于c语言,不少不错的东西”,我们可以看出这是一份关于C语言编程中的经典算法的汇编资料。虽然部分文本似乎是乱码,但从清晰的部分,我们...

    计算机自考算法设计复习资料.doc

    以下是根据提供的文件内容整理的算法设计相关知识点: 1. **算法的时间复杂度**:算法的时间复杂度是对算法执行时间与输入规模之间的关系的度量。例如,n+n*log10n2 表示的时间复杂度是 Θ(n*log n2),其中 Θ 表示...

    蓝桥杯Python组算法模板大全

    数论部分则可能包括了素数的生成、欧拉函数、扩展欧几里得算法、中国剩余定理等。这些内容在解决一些特定的算法问题时,比如密码学、大数运算中非常有用。 最后,所有这些算法模板和基础题型都来源于蓝桥云课,这是...

    数据结构与算法数据结构与算法带例题

    素数检测通常使用埃拉托斯特尼筛法或简单的试除法。埃拉托斯特尼筛法是一种用于找出一定范围内所有素数的有效方法。 3. **九九乘法表问题**:这涉及到数组的遍历和打印,可以使用二维数组来实现,按照乘法口诀的...

    vc++算法示例10个饿

    根据给定文件的信息,我们可以提炼出以下几个重要...以上就是根据给定文件信息整理出来的算法知识点。这些算法不仅在编程竞赛中非常有用,在实际项目开发中也经常会被用到。掌握它们可以帮助程序员更好地解决实际问题。

    ACM程序设计大赛算法模板 ACM模板

    《ACM程序设计大赛算法模板》是一份针对ACM(国际大学生程序设计竞赛)参赛者的重要参考资料,由计算机科学专业的鲍杭同学整理。这份模板涵盖了众多基础和高级算法,旨在帮助参赛者提升解决复杂问题的能力,提高编程...

    算法刷题笔记leetcode/lintcode

    该文档是针对LeetCode和LintCode平台上的算法题目的整理与解答,主要分为两大部分: 1. **基础概念(Basics)**:这部分介绍了数据结构、排序算法、基本算法以及位操作等计算机科学的基础知识。通过学习这些内容,...

    leetcode::notebook:算法学习笔记

    简单博弈论等),图论(dfs,bfs,溢流填充,拓扑排序,二分染色,最短,最小生成树等)系统性地学习算法会有事半功倍的效果,于是我归纳了一些基础算法的知识点,引起力扣上的相关变量进行了整理本项目的目的,是...

    acmicpc代码库 精品资料.docx

    这份文档详尽地整理了数论和图论两个核心领域的经典算法,旨在帮助参赛者提升解决问题的能力。 一、数论篇 1. 阶乘最后非零位:计算阶乘数最后的非零数字位数,通常涉及模运算和数论分析,例如高斯取整和最大公...

    大一C语言实用函数整理50+

    这份整理文档涉及了C语言编程中常用的函数和算法,主要面向编程初学者,尤其是在在线编程平台(Online Judge, OJ)上解决问题时所使用的编程技巧和函数。文档涵盖了从基础的输入输出操作、数据类型转换到较为复杂的...

Global site tag (gtag.js) - Google Analytics