素数筛(hdu 2710)-程序员宅基地

技术标签: ACM  

素数

枚举因子法

 

<strong>bool judeg(int n)
{
    if(n==1)  return false;
    for(int i=2; i*i<=n; i++)
    {
        if(n%i==0)  return false;
    }
    return true;
}</strong>

 

更准确的说应该是判断某个数是不是素数,如果做素数筛用,复杂度会很高

 

普通素数筛

 

   

 1.把1~n列出来

 2.去掉不是特殊的1

 3.从小到大,枚举每一个没有删掉的数字i

 4.把i的2倍,3倍,4倍,…,删掉

 5.剩下的没被删掉的都是素数

<strong>const int N=1000005;
bool prime[N];
void init()
{
    memset(prime,false,sizeof(prime));
    prime[1]=true;
    for(int i=2; i<N; i++)
    {
        if(prime[i]==false)
        {
            for(int j=i+i; j<N; j=j+i)    //素数的倍数全部筛去
            {
                prime[j]=true;
            }
        }
    }
}</strong>

复杂度为O(nloglogn),缺点是有的合数被删除了多次,那么如何保证每个合数只被删除一次呢?

 

素数的线性筛

 

1.列出1~n

2.删除特殊的1

3.2开始枚举数i,若没有被删掉,则加入素数表中

4.枚举素数表中的每一个素数j,并把i*j的结果从表里删去,直到枚举到j能整除i

const int N=100000005;
bool prime[N];
int a[N],k=0;      //a[N]存素数
void init()
{
    memset(prime,false,sizeof(prime));
    prime[1]=true;
    for(int i=2; i<N; i++)
    {
        if(prime[i]==false)
        {
            a[k++]=i;
        }
        for(int j=0; j<k && a[j]*i<N; j++)     //枚举素数表
        {
            prime[a[j]*i]=true;
            if(i%a[j]==0)   break;           //若该数是某个素数的倍数,则退出循环
        }
    }
}

 

if(i%a[j]==0)   break; 

这是一个很简单有效的优化,原理基于“尽量只筛一次”。 

     在这里提出“最小质因子”的概念,然后规定每个合数都只被它的最小质因子筛出————这个定义很好地契

合了“尽可能只筛一次”的想法。

     回到问题,当前如果出现"i%a[j]==0"的情况,由于枚举素数a[j]是从小到大的,那么可以说明a[j]是i的最小质因子。

     此时如果不终止循环,那么a[j+1],a[j+2]...会与i相乘得到其他的合数然后筛掉,但是该合数的最小质因子不是

该素数,然而我们使用了这个素数将其筛掉,这样做会使得一个数被筛多次,降低了效率。

例如 20应该由2 * 10筛掉,而不是被4 * 5筛掉(素数2<素数5)。

     即每一个素数都只被记录一次,每一个合数都只会被一个唯一的最小质因子标记一次因此是O(n)线性复杂度。

 

 

一道最大素数的水题  hdu 2710

 

 

Max Factor

 

                                                               Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
                                                                               Total Submission(s): 10212    Accepted Submission(s): 3292

 

 

Problem Description

To improve the organization of his farm, Farmer John labels each of his N (1 <= N <= 5,000) cows with a distinct serial number in the range 1..20,000. Unfortunately, he is unaware that the cows interpret some serial numbers as better than others. In particular, a cow whose serial number has the highest prime factor enjoys the highest social standing among all the other cows.

(Recall that a prime number is just a number that has no divisors except for 1 and itself. The number 7 is prime while the number 6, being divisible by 2 and 3, is not).

Given a set of N (1 <= N <= 5,000) serial numbers in the range 1..20,000, determine the one that has the largest prime factor.

 

 

Input

* Line 1: A single integer, N

* Lines 2..N+1: The serial numbers to be tested, one per line

 

 

Output

* Line 1: The integer with the largest prime factor. If there are more than one, output the one that appears earliest in the input file.

 

 

Sample Input

 

436384042

 

 

Sample Output

 

38

 

代码如下

 

 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int prime[20005];
void init()
{
    memset(prime,0,sizeof(prime));
    prime[1]=1;              //题中认为1也是素数
    for(int i=2; i<20005; i++)
    {
        if(prime[i]==0)
        {
            for(int j=i; j<20005; j=j+i)
            {
                prime[j]=i;              //数组里记录的是该数的最大质因子
            }
        }
    }
}
int main()
{
    int n;
    init();
    while(scanf("%d",&n)!=EOF)
    {
        int x=0,a,ans;
        while(n--)
        {
            scanf("%d",&a);
            if(prime[a]>x)
            {
                x=prime[a];
                ans=a;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

 

 

 

 

 

 

 

 

 

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/renzijing/article/details/79288023

智能推荐

06 动态分支预测技术 多指令流出技术 指令调度与循环展开_循环展开和指令调度-程序员宅基地

目录动态分支预测技术概念分支预测的有效性取决于动态分支预测技术的目的分支预测表 BHT1个预测位2个预测位BHT实现分支目标缓冲器BTB多指令流出技术工作动机多流出处理机的两种基本风格超标量超长指令字超流水线处理机指令调度与循环展开概念指令调度循环展开作用概念好处循环展开和指令调度的注意事项指令级并行总..._循环展开和指令调度

centos 6.5 php memcached,CentOS 6.5用Memcached 来作PHP 的session.save_handler_立·波的博客-程序员宅基地

php有两个memcache模块,一个是php-memcache,一个是php-memcached,php-memcached是最新的,也是比较稳定的,网上的太多的资料都是关于php-memcache的,太少提到php-memcached,而php-memcached的配置跟php-memcache是有所不同的。我的环境是多台webServer,全安装了nginx+php,3台memcached ..._session.save_handler = memcached

国家电网计算机试题百度云,2018国家电网备考资料—计算机试题-程序员宅基地

原标题:2018国家电网备考资料—计算机试题中公电网招聘网(http://www.zgdwzp.com#pj)提醒你,计算机专业的看这里,这里有计算机专业的试题,快来看看,看一眼不会吃亏不会上当哈。 1.操作系统负责为方便用户管理计算机系统的( )。A.程序 B.文档资料C.资源 D.进程1.【答案】C。解析:操作系统负责为方便用户管理计算机系统的资源。2.在首次适应算法中,要求空闲分区按( )顺...

Unity人物血条跟随 简单实现_unity血条跟随_BG_XJ的博客-程序员宅基地

这里写自定义目录标题欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注脚注释也是必不可少的KaTeX数学公式新的甘特图功能,丰富你的文章UML 图表FLowchart流程图导出与导入导出导入欢迎使用Markdown编辑器你好! 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Mar_unity血条跟随

android资料下载-程序员宅基地

全系列下载地址 http://download.csdn.net/detail/zhanglu231123/4552916 http://download.csdn.net/detail/zhanglu231123/4605414 嵌入式系统Linux内核开发实战指南 ARM平台 王洪辉 2009_12176663.part1http://download.csdn.net/detail

v-on指令详解_v-on显示鼠标的坐标-程序员宅基地

获取点击事件元素本身< button type=“button” @click=“click1($event)”>按钮< /button>methods : { click1() { …} }console.log(e);//返回一个鼠标事件对象MouseEvent。console.log(e.target);//通过对象的target来获取触发事件的对象。console.log(e.clientX);//通过对象的target来获取鼠标的相对坐标值X。&l._v-on显示鼠标的坐标

随便推点

使用n模块更新node换国内源方法_error: download preflight failed for '18.16.1' (ht_<!>的博客-程序员宅基地

问题出现昨天用 n 更新 node 的时候,一直出现下载不动的问题。也出现了诸如 Error: download preflight failed for ‘14.18.1’ (https://nodejs.org/dist/v14.18.1/nod e-v14.18.1-linux-x64.tar.xz)等问题。感觉应该是源的问题,网上说换源的貌似很少,就去github查了一下。解决方法这里以更换淘宝源为例。在linux下直接运行export N_NODE_MIRROR=https:/_error: download preflight failed for '18.16.1' (https://nodejs.org/dist/v18.

我之所以抛弃Java而选择Kotlin的10个理由-程序员宅基地

新事物或者新技术的出现虽然不一定要替代旧技术,但是它的到来是无可阻挡的。就像拥有黑白电视的人,当彩色电视出现了,他们可以选择是否替换为彩色电视,却无法阻止彩色电视的诞生。科技是一个很玄妙的事实,总会出现一个新的技术来挑战长期建立好的秩序,就像之前我们在谈论Android开发时,Java是主要的编程语言,但是其实有很多可用于编写Android应用程序也符...

img video 等比例缩放的特性_video标签等比缩放-程序员宅基地

img 和 video的宽度固定后,高度会随宽度进行等比例缩放_video标签等比缩放

cx_Oracle库导入失败引起crontab中python程序运行失败,并且无错误提示-程序员宅基地

今天遇到一个问题: 一个python脚本命令行运行时很正常,放到crontab中就无法工作,日志也没有记录,找了半天,终于发现问题所在。在脚本最上方,程序如下:#!/usr/local/bin python # coding=utf8 import cx_Oracle import sys import time 注意,这里import cx_...

静态链表简介_静态链表长度还能增加吗-程序员宅基地

静态链表在存储结构上将使用的是整块的连续的存储空间,而普通链表是零散的并非连续的存储空间。 采用数组的形式构建链表,打破了之前的“数组”与“链表”的区别,在增加删减结点的时候巧妙运用了链表的结构思想,可以看作 "数组形式的链表",下面给出详细的部分代码。struct StaticLinkList {private: string data ; int cur ; int n ;public: StaticLinkList(int a) :data(""), cur(0),n(a) {}._静态链表长度还能增加吗

【迁移学习】STL(Stratified Transfer Learning)小结-程序员宅基地

STL(Stratified Transfer Learning)分层迁移学习:问题描述提出了一个CDAR的问题:源域和目标域数据具有相同的维度、相同的标记,但是P(Xs)不等于 P(Xt)同时P(Ys|Xs)不等于P(Yt|Xt)。交叉领域学习的目标是利用源域的标记和数据来获取标记Yt。整体farmworke 分为三个部分:Majority VotingIntra-class Tran...