【蓝桥杯2025备赛】素数判断:从O(n^2)到O(n)学习之路

素数判断:从O( n 2 n^2 n2)到O(n)学习之路

背景:每一个初学计算机的人肯定避免不了碰到素数,素数是什么,怎么判断?

素数的概念不难理解:素数即质数,指的是在大于1的自然数中,除了1和它本身不再有其他因数的自然数。

如何判断

刚进大学时,我最开始接触的就是最简单的那种,比较容易理解,但复杂度较高,容易超时

暴力写法

#include <iostream>
using namespace std;

int primes[10000];
int main()
{
	int cnt = 0,n=1000;
	for (int i = 2; i < n; i++)
	{
		int temp = 0;//假定是素数
		for (int j = 2; j < i; j++)
		{
			if (i % j == 0) { temp = 1; break; }//只要i能整除j,那肯定不是质数,temp=1标记为合数
		}
		if (!temp)primes[cnt++] = i;
	}
	for (int i = 0; i < 20; i++)cout << primes[i] << " ";
}

时间复杂度:O( n 2 n^2 n2​​)

之后有看了网上的一些写法,学了些优化的方法

比如,我们判断到 n \sqrt n n 就可以结束了,为什么可以这样呢?

下面的这个图或许可以说明这一点

在这里插入图片描述

#include <iostream>
using namespace std;

int primes[10000];
int main()
{
	int cnt = 0, n = 1000;
	for (int i = 2; i <n; i++)
	{
		int temp = 0;//假定是素数
		if (i > 2 && i % 2 == 0)continue;//大于2的偶数肯定不是素数
		for (int j = 2; j*j<=i; j++)//这个地方可以写成j<=sqrt(i);但调用函数会慢一点
            //其次,写成乘法,而尽量不写j<=i/j;,乘法比除法更快
		{
			if (i % j == 0) { temp = 1; break; }//只要i能整除j,那肯定不是质数,temp=1标记为合数
		}
		if (!temp)primes[cnt++] = i;
	}
	for (int i = 0; i < 20; i++)cout << primes[i] << " ";
}

终极大法:欧拉线性筛

时间复杂度:O( n n n​)

关于这方面的解释,我找了下知乎大佬的解释,我自己大概明白了基本原理,但并不能很好的阐述它

废话不多说,上图!!!
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

img

const int N=100000;
int primes[N];//质数表,是质数的加入其中
bool st[N];//false表示素数,true为非素数
void get_primes(int N)//利用线性筛找到2~n中的质数
{
    int cnt=0;st[0]=true;st[1]=true;//0和1为非素数
    for(int i=0;i<=N;i++)
    {
        if(!st[i])primes[cnt++]=i;//如果没被筛掉,是质数,假如质数表
        for(int j=0;i*primes[j]<=N;j++)
        {
            st[i*primes[j]]=true;//用最小质因子去筛素数
            if(i%primes[j]==0)break;
        }
    }
}

OK,让我们来道题试试吧

X的因子链

输入正整数$ X$,求 X X X 的大于 11 的因子组成的满足任意前一项都能整除后一项的严格递增序列的最大长度,以及满足最大长度的序列的个数。

输入格式

输入包含多组数据,每组数据占一行,包含一个正整数表示 X X X

输出格式

对于每组数据,输出序列的最大长度以及满足最大长度的序列的个数。

每个结果占一行。

数据范围

1 ≤ X ≤ 2 20 1≤X≤2^{20} 1X220

输入样例:
2
3
4
10
100
输出样例:
1 1
1 1
2 1
2 2
4 6
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=(1<<20)+5;
int primes[N];bool st[N];
int minp[N];
void get_primes()//线性筛质数
{
    int cnt=0;
    for(int i=2;i<=N;i++)
    {
        if(!st[i]){primes[cnt++]=i;minp[i]=i;}//记录最小质因数
        for(int j=0;primes[j]*i<=N;j++)
        {
            st[primes[j]*i]=true;
            minp[primes[j]*i]=primes[j];//最小质因数
            if(i%primes[j]==0)break;
        }
    }
}
int main()
{   
    int x;
    get_primes();
    while(scanf("%d",&x)!=EOF)
    {
     int k=0;int total=0;int sum[10]={0};//初始化数组
     while(x>1)//数的分解,用最小质因数去分解
     {  
        
        int t=minp[x];sum[k]=0;//我要用到的时候再重置为0,没用到的数据不为0没关系,因为遍历时数组只会遍历到k
         //而这k个数据在这里已经被重置后进行运算
        while(x%t==0)
        {
          sum[k]++;
          total++;
          x/=t;
        }
        k++;
     }
     ll res=1;
     for(int i=2;i<=total;i++)res*=i;//总的阶乘
     for(int j=0;j<k;j++)
      for(int i=1;i<=sum[j];i++)res/=i;
      
     printf("%d %lld\n",total,res);
     memset(sum,0,sizeof(sum));//注意,这里开了memset会超时的,10^6的长度数组有100组数据就会运算10^8次了,容易超时
    }                          //当然,我们数组开到10然后重置是不会超时的,
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/555189.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

4.18作业

顺序栈&#xff1a; #include "seq_stack.h" seq_p creat_stack() //从堆区申请顺序栈的空间 {seq_p S(seq_p)malloc(sizeof(seq_stack));if(SNULL){printf("空间申请失败\n");return NULL;}bzero(S->data,sizeof(S->data));S->top-1;return S; …

OpenGL:图元

OpenGL的图元 点 GL_POINTS: 将顶点绘制成单个的点 线 GL_LINES:将顶点用于创建线段,2个点成为一条单独的线段。如果顶点个数是奇数,则忽略最后一个。 顶点:v0, v1, v2, v3, … , vn,线段:v0-v1, v2-v3, v4-v5, … , vn-1 - vn GL_LINE_STRIP:将顶点用于创建线段,…

在Linux系统中,禁止有线以太网使用NTP服务器进行时间校准的几种方法

目录标题 方法 1&#xff1a;修改NTP配置以禁止所有同步方法 2&#xff1a;通过网络配置禁用NTP同步方法 3&#xff1a;禁用NTP服务 在Linux系统中&#xff0c;如果想要禁止有线以太网使用NTP服务器进行时间校准&#xff0c;可以通过以下几种方法之一来实现&#xff1a; 方法 …

tcp网络编程——2

1.一个服务器只能有一个客户端连接&#xff08;下面代码&#xff09; ​​​​​​​tcp网络编程&#xff08;基础&#xff09;-CSDN博客 2.一个服务器可以有多个客户端连接&#xff08;多线程&#xff09; server端创建多个线程&#xff0c;每个线程与不同的client端建立连…

代码签名证书的作用及申请

代码签名证书新兴的数字证书的一种&#xff0c;应用范围相对于传统的数字证书而言要稍微少一些。用于验证软件代码的来源和完整性&#xff0c;并提供了一种防止代码被篡改或损坏的机制。常用于软件开发上&#xff0c;代码签名证书由签名证书公钥和私钥证书两部分组成&#xff0…

day05-Elasticsearch01

1.初识elasticsearch 1.1.了解ES 1.1.1.elasticsearch的作用 elasticsearch 是一款非常强大的开源搜索引擎&#xff0c;具备非常多强大功能&#xff0c;可以帮助我们从海量数据中快速找到需要的内容 例如&#xff1a; 在 GitHub 搜索代码在电商网站搜索商品在百度搜索答案在打…

【工位ubuntu的配置】补充

软件 安装桌面图标的问题 登录密码 root的密码为&#xff1a;19980719 按照如下的链接进行配置&#xff1a; https://blog.csdn.net/zhangmingfie/article/details/131102331?spm1001.2101.3001.6650.3&utm_mediumdistribute.pc_relevant.none-task-blog-2%7Edefault%7E…

永久免费次数ChatGPT国内镜像网站【强烈建议收藏】

gctohttps://chat.tomyres.com/#/pages/web/index?n0 觉得分享的网站好用的话&#xff0c;记得点赞收藏哦。

lettcode179.最大数

问题描述&#xff1a; 给定一组非负整数 nums&#xff0c;重新排列每个数的顺序&#xff08;每个数不可拆分&#xff09;使之组成一个最大的整数。 注意&#xff1a;输出结果可能非常大&#xff0c;所以你需要返回一个字符串而不是整数。 示例一&#xff1a; 输入nums [10…

街景图片语义分割后像素类别提取,用于计算各种指标。

语义分割代码见之前博文&#xff08;免费&#xff09;&#xff1a;deeplabv3街景图片语义分割&#xff0c;无需训练模型&#xff0c;看不懂也没有影响&#xff0c;直接使用。cityscapes 语义分割之后&#xff0c;如下图&#xff0c;想要统计各类像素所占的比例&#xff0c;用于…

2024 MathorCup C 题 物流网络分拣中心货量预测及人员排班

一、问题重述 电商物流网络在订单履约中由多个环节组成&#xff0c;图1是一个简化的物流网络示意图。其中&#xff0c;分拣中心作为网络的中间环节&#xff0c;需要将包裹按照不同流向进行分拣并发往下一个场地&#xff0c;最终使包裹到达消费者手中。分拣中心管理效率的提升&…

初识 React:安装和初步使用指南

文章目录 前言一、React 是什么&#xff1f;1.组件化开发2.虚拟 DOM3.单向数据流4.生态系统丰富 二、安装1.准备工作2.下载react 三、探索 React 应用总结 前言 在当今的 Web 开发领域&#xff0c;React 已经成为了一个备受推崇的技术。它的组件化、灵活性和高效性使得它成为了…

MySQL中InnoDB的行级锁

InnoDB 实现了以下两种类型的行锁。 共享锁&#xff08;S&#xff09;&#xff1a;又称为读锁&#xff0c;简称S锁&#xff0c;共享锁就是多个事务对于同一数据可以共享一把锁&#xff0c;都能访问到数据&#xff0c;但是只能读不能修改。 排他锁&#xff08;X&#xff09;&am…

时间同步服务项目练习

一.配置server主机要求如下&#xff1a; 1.server主机的主机名称为 ntp_server.example.com 2.server主机的IP为&#xff1a; 172.25.254.100 3.server主机的时间为1984-11-11 11&#xff1a;11&#xff1a;11 4.配置server主机的时间同步服务要求可以被所有人使用 更改主机名…

Android开发基础:Activity之间的跳转 向下一个Activity传递数据 给上一个Activity返回数据

目录 一&#xff0c;使用Intent在Activity之间跳转 1.显示使用Intent 2.隐式使用Intent 二&#xff0c;携带数据的跳转 1.Bundle 三&#xff0c;返回数据给上一个Activity 1.registerForActivityResult 一&#xff0c;使用Intent在Activity之间跳转 一个Android应用中包…

APEX开发过程中需要注意的小细节5.5

oracle保留小数点后两位的函数 在日常开发中经常用到百分比做数据对比&#xff0c;但是有可能得到的数据是一个多位小数&#xff0c;结果如下所示&#xff1a; 如果想截取部分小数如保留小数点后两位可以怎么做呢&#xff1f; 在Oracle中&#xff0c;可以使用ROUND函数来四舍…

请警惕,这10本期刊已被SCI剔除,部分涉嫌灌水

科睿唯安于4月15日更新了SCIE、SSCI、AHCI、ESCI四大数据库最新收录期刊目录。 2024年第一版——2024年1月24日更新 2024年第二版——2024年2月19日更新 2024年第三版——2024年3月18日更新 2024年第四版——2024年4月15日更新 本次目录中共收录期刊23368本。 【SCIE数据…

档案集中管理的痛点怎么解决?

档案集中管理可能面临的痛点包括以下几个方面&#xff1a; 1. 档案分类和整理困难&#xff1a;档案集中管理会面临大量档案的分类和整理工作&#xff0c;可能导致混乱和困难。 解决方法&#xff1a; - 建立统一的档案分类规范和流程&#xff0c;确保所有档案都能按照规定的方式…

《QT实用小工具·二十九》托盘图标控件

1、概述 源码放在文章末尾 托盘图标控件 可设置托盘图标对应所属主窗体。 可设置托盘图标。 可设置提示信息。 自带右键菜单。 下面是demo演示&#xff1a; 项目部分代码如下&#xff1a; #ifndef TRAYICON_H #define TRAYICON_H/*** 托盘图标控件* 1. 可设置托盘图标…

Unity类银河恶魔城学习记录12-17 p139 In game UI源代码

Alex教程每一P的教程原代码加上我自己的理解初步理解写的注释&#xff0c;可供学习Alex教程的人参考 此代码仅为较上一P有所改变的代码 【Unity教程】从0编程制作类银河恶魔城游戏_哔哩哔哩_bilibili UI.cs using UnityEngine;public class UI : MonoBehaviour {[SerializeFie…