文档章节

Eratosthenes 筛选求质数

datacube
 datacube
发布于 2016/07/07 11:14
字数 471
阅读 8
收藏 0

import java.util.Scanner;

public class Eratosthenes {

    static void getPrimes(int num){
        int []arr = new int[num +1];//长度为11的数组,能够存下表为0-10的数组,所以取10以内的数组,需要申请11长度的数组
        for (int i = 1; i <= num; i++){
            arr[i] = i;
        }
        arr[1] = 0;//1不是素数,排除1

        for (int i = 2; i < Math.sqrt(num); i++){
            for (int j = i+1; j < num; j++){
                if (arr[j] != 0 && arr[j]%i == 0){
                    arr[j] = 0;
                }
            }
        }

        for (int i = 0; i < num; i++){
            if (arr[i] != 0){
                System.out.printf(arr[i]+"\t");
            }
        }
    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.printf("请输入查询值:");
        int num = scanner.nextInt();
        getPrimes(num);



    }
}

===============================


import java.util.Scanner;

public class CheckPrime {


    static boolean isCheck(int x){
        for (int i = 2; i < x; i++){
//        for (int i = 2; i <= Math.sqrt(x); i++){
            if (x % 2 == 0){
                return false;
            }
        }
        return true;

    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int x = scanner.nextInt();
        System.out.println(isCheck(x));
    }
}
/**
 * 2是素数,1不是素数
 *
 * 排除异常树
 * if(n < 2) return false;
 *
 * 偶数一定不适素数
 * if(n%2==0) return false;
 *
 * 定理: 如果n不是素数, 则n有满足1< d<=sqrt(n)的一个因子d.
  证明: 如果n不是素数, 则由定义n有一个因子d满足1< d< n.
  如果d大于sqrt(n), 则n/d是满足1< n/d<=sqrt(n)的一个因子.

   sqrt()是开方,开方的两个数是相等的,4*4=14,如果一个数大约平方根,那么另一个数一定小于平方根,才能满足二者的乘积等于两个平方根的积


 1、素数及相关

 素数,又称质数,在一个大于1的自然数中,除了1和此整数自身之外,不能被其他自然数整除的数。
 比1大但不是素数的数称为合数。
 1和0既不是素数,也不是合数。
 算术基本定理证明每个大于1的正整数都可以写成素数的乘积,并且这种乘积的形式是唯一的。


 */

© 著作权归作者所有

下一篇: 最长公共子串
datacube
粉丝 9
博文 607
码字总数 152394
作品 0
海淀
程序员
私信 提问
极少数人用过的另类素数求解法,C语言经典算法之筛选法求质数

筛选求质数 明除了自身之外,无法被其它整数整除的数称之为质数,要求质数很简单,但如何快速的求出质数则一直是程式设计人员与数学家努力的课题,在这边介绍一个着名的 Eratosthenes求质数方...

这个人很懒什么都没留下
03/28
0
0
数论基础 扩展欧几里得 线性筛 逆元 欧拉函数 Lucas定理

扩展欧几里得 欧几里得算法,又叫辗转相除法,用于求两个数的最大公约数(gcd)。 由此可以得到最小公倍数 (先除防止溢出)。 扩展欧几里得,是用于解出方程 的一组解的。比如方程 ,可以解...

myjs999
2017/10/25
0
0
LeetCode:Count Primes - 统计质数数量

1、题目名称 Count Primes(统计质数数量) 2、题目地址 https://leetcode.com/problems/count-primes/ 3、题目内容 英文:Count the number of prime numbers less than a non-negative nu......

北风其凉
2015/09/06
845
0
python leetcode-204 Count Primes 质数计数

title: "leetcode-204 Count Primes 质数计数" 我的博客 https://zszdata.com/2019/03/09/count-primes/ Count Primes Count the number of prime numbers less than a non-negative number,......

sz88888
04/08
0
0
Scala 2.10 和 2.9.2 的性能比较

我已经阅读了 Scala 2.10.0-RC3 的一些新特性,该版本最值得关注的就是性能方面的提升,我很好奇这个提升的幅度到底有多大,于是我做了一个基准测试。下面是我的两个测试用的代码: Eratosth...

红薯
2012/12/03
4.5K
13

没有更多内容

加载失败,请刷新页面

加载更多

sync.Mutex 互斥锁

说明: 互斥锁用来保证在任一时刻,只能有一个例程访问某对象。Mutex 的初始值为解锁状态。Mutex 通常作为其它结构体的匿名字段使用,使该结构体具有 Lock 和 Unlock 方法。Mutex 可...

李琼涛
27分钟前
6
0
自建redis笔记

自建redis笔记 最近在linux安装了一下redis,特做一些笔记! 本文先单节点启动redis,然后再进行持久化配置,在次基础上,再分享搭建主从模式的配置以及Sentinel 哨兵模式及集群的搭建 单节点...

北极之北
30分钟前
4
0
扛住阿里双十一高并发流量,Sentinel是怎么做到的?

Sentinel 承接了阿里巴巴近 10 年的双十一大促流量的核心场景 本文介绍阿里开源限流熔断方案Sentinel功能、原理、架构、快速入门以及相关框架比较 基本介绍 1 名词解释 服务限流 :当系统资源...

分布式系统架构
31分钟前
5
0
事假杨晨龙(Z16021)月薪请假单

svn co URL --username xxx-- password yyy ./

桃花飞舞
55分钟前
7
0
当Activity关闭后,网络请求回调的处理

当我们在使用网络请求的时候,一般都是通过回调来获取请求到的数据。对于网络请求的回调需要注意的几个点 比如我们的回调在Activity中处理数据,当我们把Activity关闭后,如果获取到数据时,...

shzwork
56分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部