文档章节

关于判断素数的一些算法

Hosee
 Hosee
发布于 2015/05/16 14:56
字数 434
阅读 233
收藏 0

最近在hdu上A题

碰到些素数问题,记录下看到的算法。


一、筛选法

题目:http://acm.hdu.edu.cn/showproblem.php?pid=2136


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class Main
{
    public static void main(String[] args) throws IOException
    {
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(
                new InputStreamReader(System.in)));
        int[] arr = new int[1000001];
        int count = 1;
        int temp;
        for (int i = 2; i < 1000000; i++)
        {
            if (arr[i] == 0)//只用判断不被前面“筛选掉的数字”
            {
                temp = i;
                while (temp < 1000000)//这里就是筛选数字,把i的整数倍的数字都挖掉
                {                     //因为肯定有因子i,则一定不是素数。
                    arr[temp] = count;//此处的赋值是因为题目的要求有点小改变,筛选法只用分别出素数和非素数
                    temp = temp + i;
                }
                count++;
            }

        }
        int n;
        while (st.nextToken() != StreamTokenizer.TT_EOF)
        {
            n = (int) st.nval;
            System.out.println(arr[n]);
        }
    }
}



思想很简单:



<1> 先将1挖掉(因为1不是素数)。
<2> 用2去除它后面的各个数,把能被2 整除的数挖掉,即把2的倍数挖掉。
<3> 用3去除它后面的各数,把3的倍数挖掉。
<4> 分别用5…各数作为除数去除这些数以后的各数。
上述操作需要一个很大的容器去装载所有数的集合,只要满足上述条件,即2的倍数大于1的全部置0,3的倍数大于1的全部置0,4的倍数大于1的全部置0.。。。一直到这个数据集合的末尾,这样一来不为0的数就是素数了,然后按下标在里面进行查找就好了



二、米勒拉宾算法

算法思想:http://www.cnblogs.com/skyivben/archive/2010/07/10/1775001.html

看了一下看不懂,记录下有这种算法思想。


© 著作权归作者所有

Hosee
粉丝 608
博文 135
码字总数 209956
作品 0
杭州
程序员
私信 提问
考研复试系列——第九节 数论基础

考研复试系列——第九节 数论基础 引言 该部分内容来源于 《王道论坛》 。 写个算法,对 2 个小于 1000000000 的输入,求结果。 特殊乘法举例:123 45 = 14 +15 +24 +25 +34+3*5 样例输入: ...

cassiepython
2017/03/09
0
0
Python进阶系列连载(13)——Python内置高阶函数filter(下)

前言 进阶部分连载继续~ 如果还没看过我的入门连载部分,先看: https://ask.hellobi.com/blog/wangdawei/10288 当然,小编的免费入门课程已经有咯,看过连载的朋友可以看看视频再快速梳理一...

ID王大伟
2018/04/28
0
0
LeetCode算法题-Prime Number of Set Bits in Binary Representation(Java实现)

这是悦乐书的第311次更新,第332篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第180题(顺位题号是762)。给定两个正整数L和R,在[L,R]范围内,计算每个整数的二进制数中1的...

小川94
04/20
0
0
素数在两种常见情况下的标准最优算法

素数在两种常见情况下的标准最优算法 方法名称 相邻剪枝法 通过判断待验证数是否在6的两侧而进行剪枝(2与3除外),验证单个数字时常用。 下述代码中原型体现为prime_1() 素数筛法 依据每个素...

read_me
07/17
0
0
LeetCode算法题-Count Primes(Java实现)

这是悦乐书的第190次更新,第193篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第49题(顺位题号是204)。计算小于非负数n的素数的数量。例如: 输入:10 输出:4 说明:有4...

小川94
2018/12/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

为什么要在网站中应用CDN加速?

1. 网页加载速度更快 在网站中使用CDN技术最直接的一个好处就是它可以加快网页的加载速度。首先,CDN加速的内容分发是基于服务器缓存的,由于CDN中缓存了不少数据,它能够给用户提供更快的页...

云漫网络Ruan
42分钟前
7
0
亚玛芬体育(Amer Sports)和信必优正式启动合作开发Movesense创新

亚玛芬体育和信必优正式启动合作开发Movesense创新,作为亚玛芬体育的完美技术搭档,信必优利用Movesense传感器技术为第三方开发移动应用和服务。 Movesense基于传感器技术和开放的API,测量...

symbiochina88
53分钟前
4
0
创龙TI AM437x ARM Cortex-A9 + Xilinx Spartan-6 FPGA核心板规格书

SOM-TL437xF是一款广州创龙基于TI AM437x ARM Cortex-A9 + Xilinx Spartan-6 FPGA芯片设计的核心板,采用沉金无铅工艺的10层板设计,适用于高速数据采集和处理系统、汽车导航、工业自动化等领...

Tronlong创龙
54分钟前
4
0
好程序员Java学习路线分享MyBatis之线程优化

  好程序员Java学习路线分享MyBatis之线程优化,我们的项目存在大量用户同时访问的情况,那么就会出现大量线程并发访问数据库,这样会带来线程同步问题,本章我们将讨论MyBatis的线程同步问...

好程序员官方
今天
6
0
IDEA 自定义方法注解模板

IDEA 自定义方法注解模板 1、使用效果 /*** 计算交易费用* @Author wangjiafang* @Date 2019/9/11* @param feeComputeVo* @return*/@PostMapping("/v1/fee_compute")public ApiResp......

小白的成长
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部