质因数算法(C/C++)

这篇具有很好参考价值的文章主要介绍了质因数算法(C/C++)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

1  分解质因数

2  打印质数表

2.1  O(n^2)算法(暴力法)

2.2  O(nlogn)算法(埃氏筛)

2.3  O(n)算法(线性筛)

3  计算因数和


1  分解质因数

#include <bits/stdc++.h>
using namespace std;
int num,temp;
int main()
{
	scanf("%d",&num);
	temp=num;//保护 
	for(int i=2;i<=temp;i++)
	{
		while(num%i==0)
		{
			printf("%d ",i);
			num/=i;
		}
	}
	return 0;
}

说明:这里不需要担心没有筛选质数的问题,因为是从小到大循环,不可能存在分解出合数的情况(例如:2第一个循环,所有2的倍数都已经被筛选掉了,后续循环不可能再有2的倍数被num整除)

2  打印质数表

2.1  O(n^2)算法(暴力法)

两层循环,第一层循环i遍历大于等于2的所有数,第二层循环遍历大于1小于i的所有数j,判断i%j!=0一直成立,则该数为质数

这种方法虽然思路简单,但时间复杂度有时不能满足题目要求

2.2  O(nlogn)算法(埃氏筛)

定理:一个质数*任何一个不为1的正整数=合数

有了定理之后,就可以通过定理优化代码降低时间复杂度,下面是具体思路

Eratosthenes筛选方法(Eratosthenes Sieve Method)

假设有一个筛子存放1~N,例如:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 .........N

先将  2的倍数  筛去:

2 3 5 7 9 11 13 15 17 19 21..........N

再将  3的倍数  筛去:

2 3 5 7 11 13 17 19..........N

 之后,再将5的倍数筛去,再来将7的质数筛去,再来将11的倍数筛去........,如此进行到最后留下的数就都是质数,这就是Eratosthenes筛选方法(Eratosthenes Sieve Method)。

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int primes[1000000];
int cnt;
bool notprime[1000000];

void set_prime()
{
	notprime[1]=true;
	for(int i=2;i<1000000;i++)
	{
		if(!notprime[i])
		{
			primes[++cnt]=i;
		}
		for(ll j=(ll)i*i;j<1000000;j+=i)//保证每一个遍历的值都没被筛过
		{
			notprime[j]=true;
		}
	}
} 

int main()
{
	set_prime();
	for(int i=1;i<=cnt;i++)
	{
		cout<<primes[i]<<endl;
	}
	return 0;
}

质因数算法(C/C++)

 模拟发现,有一些数被筛了不止一次,可能还有更优解

2.3  O(n)算法(线性筛)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int primes[1000000];
bool notprime[1000000];
int cnt,n;
int main()
{
	cin>>n;//打印范围 
	for(int i=2;i<=n;i++)
	{
		if(!notprime[i])	primes[++cnt]=i;
		for(int j=1;j<=cnt&&i*primes[j]<=n;j++)
		{
			notprime[i*primes[j]]=true;
			if(i%primes[j]==0)	break;
		}
	}
	for(int i=1;i<=cnt;i++)
	{
		cout<<primes[i]<<endl; 
	}
	return 0;
} 
	

3  计算因数和

直接上例题:

寻找完数
【问题描述】
完数是指一个整数恰好等于它的因子和(除自身外),则称这个数为完数。从键盘先后输入两个不大于999的正整数m和n,若m>n,则交换两数,然后求m和n之间(m和为正数且m≤n)的所有完数
【输入形式】
先后输入两个正整数m和n,用逗号分隔
【输出形式】
输出所有完数,每两个数之间用号分隔若输入非法,则输出error
【样例输入】
1,2000 
【样例输出】
6,28,496
【样例说明】

【评分标准】
正确性

注意:没有考虑输出的逗号(处理方法:第一个数单独输出)

#include<bits/stdc++.h>
using namespace std;
int m,n,j,i;

bool factorSum(int n)
{
	int sum=0;
    for (i=1;i*i<=n;i++)
	{
        if (n%i==0&&n!=i)
		{
            if (i==1||i*i==n) sum+=i;
            else	sum+=i+n/i;
        }
    }
    return j==sum;
}

int main()
{
	scanf("%d,%d",&m,&n);
	if(m<=0||n<=0||m>9999||n>9999)
	{
		printf("error");
		return 0;
	}
	if(m>n)
	{
		swap(m,n);
	}
	for(j=m;j<=n;j++)
	{
		if(factorSum(j)) printf("%d,",j);
	}
	return 0;
}

4  补充:蓝桥杯简介


一. 蓝桥杯赛事简介

蓝桥杯全国软件和信息技术专业人才大赛,是由工业和信息化部人才交流中心举办的全国性IT学科赛事。全国1200余所高校参赛,累计参赛人数超过40万人。蓝桥杯大赛连续两年被列入中国高等教育学会发布的“全国普通高校学科竞赛排行榜”,是高校教育教学改革和创新人才培养的重要竞赛项目。对大学生综合评测,奖学金评定,升学考研都有一定助益。

大赛共包括三个竞赛组别,个人赛-软件类,个人赛-电子类,以及视觉艺术大赛。其中个人赛-软件类的比赛科目包括C/C++程序设计、Java软件开发、Python程序设计。今年第十二届蓝桥杯报名时间是2020年12月-2021年3月,4月省赛,5月国赛。

蓝桥杯大赛已成功举办11届,成为国内始终领跑的人才培养选拔模式,并受到行业和企业的高度认可,含金量也逐年增加,主要体现在:

蓝桥杯大赛题目的专业度高,专业度和难度已经与国际国内知名程序设计类竞赛不相上下。

双一流大学的参与度逐年提高,以最近的第11届蓝桥杯大赛为例,来自双一流大校的参赛选手近10000名;

专业顶尖选手越来越多,对历年选手的跟踪回访,发现大赛选手与ACM参赛选手高度重叠,可谓赢家通吃。

二. 参加蓝桥杯的好处

大学,是人生中最美最重要的时段。在大学,有的人经历苍白,有的人经历丰富,究竟是苍白还是丰富,取决于人的选择。如果你是IT类的学生,那么,我建议你了解并参加蓝桥杯大赛。既然我这么建议,那肯定是有道理的,比如:

1. 可以丰富自己的大学经历

有的人,在大学失去了方向和斗志,浑浑噩噩,当初信誓旦旦要从事IT相关领域,最后发现,是从事打游戏这个领域,毕业前才发现,自己所学甚少。 而蓝桥杯大赛,恰好可以让你丰富自己的大学经历,不枉费专业,不虚此行。

2. 可以提供自己的实力和水平

有不少同学是很有上进心的,但苦于不知道怎么发力。那么,蓝桥杯大赛,能给你指引好方向,让你处在竞争的氛围中,牵引着你向前。通过大赛实战,不断地检验和完善自己,经历挫败和曲折后,获得成功,这种经历,尤为珍贵。

3. 可以为将来的职业铺好道路

大家都是要去求职的,在面试中,最忌讳的就是,拿不出曾经的经历和成绩,无法打动面试官和公司。有的人在面试时,只说自己爱好学习,但拿不出任何证据。相反,如果参加蓝桥杯这样的大赛,成功也好,失败也好,至少来讲,你比别人多了一块敲门砖,面试官也会对你刮目相看。

三. 蓝桥杯的备战攻略

蓝桥杯大赛,含金量在不断上升,参与的人数也在逐渐增多。前面说了,蓝桥杯大赛是个人赛,相对来说参加门槛低,分组的赛制对参赛选手也更加友好。但是,这并不意味着你可以高枕无忧。毕竟,没有人能随随便便成功。攻略和建议如下:

第一,当然是报名啦。有的朋友,准备得很充分,准备上战场的时候,才发现忘了报名或者错过报名时间。如果院校不组织参加,自己也可以选择个人报名,千万别忘记到官网报名。否则一失足成心头恨,再回首已是深秋。

第二,要充分掌握竞赛设涉及到的一些语言,熟练使用一些API, 这些东西,并不需要你死记硬背(比赛会提供相关的API说明),但肯定要有一个大概的印象。

第三,算法很重要,很重要,很重要。自己平时可以多找一些算法相关的书籍看看,对常用常见常考的算法,做到了如指掌,这样才能才大赛时随机应变。

第四,搞懂了基本的算法之后,还得实战,那就要大量刷题,刷题,刷题。蓝桥杯大赛官网有历年真题,只有通过大量刷题,才能举一反三,触类旁通,即使大赛遇到陌生题目,也不担心。

四. 关于蓝桥杯的结语

人生本来就是各种经历,大学是人生中最美好的阶段,对于身处IT浪潮中的同学而言,愿大家不负韶华,珍惜机会,丰富经历。希望有志青年,在蓝桥杯大赛中,碰撞出璀璨的智慧火花。
 文章来源地址https://www.toymoban.com/news/detail-406333.html

到了这里,关于质因数算法(C/C++)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【c语言】--分解质因数【完整版详细】

    首先,我们所说的质数就是素数,两种叫法都可以! 如果一个数的因数是质数,那么这个因数就是他的质因数。 比如: 5的因数:1、5 因数5就是5的质因数。 28的因数:4、7 因数7就是28的质因数。 把一个合数用质数相乘的形式表示出来,叫作分解质因数。他强调的是分解的过

    2024年02月06日
    浏览(39)
  • 洛谷——P1069 [NOIP2009 普及组] 细胞分裂(分解质因数,唯一分解定理)

    Hanks 博士是 BT(Bio-Tech,生物技术)领域的知名专家。现在,他正在为一个细胞实验做准备工作:培养细胞样本。 Hanks 博士手里现在有 N N N 种细胞,编号从 1 ∼ N 1 sim N 1 ∼ N ,一个第 i i i 种细胞经过 1 1 1 秒钟可以分裂为 S i S_i S i ​ 个同种细胞( S i S_i S i ​ 为正整数)。

    2024年01月16日
    浏览(46)
  • 质因数算法(C/C++)

    目录 1  分解质因数 2  打印质数表 2.1  O(n^2)算法(暴力法) 2.2  O(nlogn)算法(埃氏筛) 2.3  O(n)算法(线性筛) 3  计算因数和 说明:这里不需要担心没有筛选质数的问题,因为是从小到大循环,不可能存在分解出合数的情况(例如:2第一个循环,所有2的倍数都已

    2023年04月09日
    浏览(35)
  • 蓝桥杯双周赛算法心得——铺地板(质因数)

    大家好,我是晴天学长,这是第二周的蓝桥杯的双周赛,题可出的又好又灵活啊!真不错!💪💪💪 1) .铺地板 2) .算法思路 1.导入java.util包中的Scanner类,以从用户那里读取输入。 2.main方法是程序的入口点。 3.创建一个Scanner对象,用于从标准输入读取输入。 4.从用户那里读取

    2024年02月08日
    浏览(40)
  • 试题 C: 质因数个数

    萎了,整个人都萎了 快三天都没刷题了,想着明天就蓝桥杯了,就找了个真题做了下 可以看得出来这题很简单 但是没有测试点给我用,所以我的代码不保证正确性 代码如下:

    2024年04月13日
    浏览(35)
  • Python中查找质因数

    如何在Python中进行素因式分解。 在数学中,一个数的因数是指那些可以除以给定数并留下零余数的数字。 质数是只有两个因数的独特数字,一个和数字本身。这类数字的一些例子是3,7,11,13,等等。 素数因数化是指找到所有乘以原数的素数。我们可以考虑一个简单的例子:数字

    2024年02月10日
    浏览(44)
  • [保研/考研机试] KY7 质因数的个数 清华大学复试上机题 C++实现

    求正整数N(N1)的质因数的个数。 相同的质因数需要重复计算。如120=2*2*2*3*5,共有5个质因数。 输入描述: 可能有多组测试数据,每组测试数据的输入是一个正整数N,(1N10^9)。 输出描述: 对于每组数据,输出N的质因数的个数。 输入: 输出: 只需要判断因数是否能够整除当前

    2024年02月13日
    浏览(45)
  • C. Multiplicity(DP + 分解因数)

    Problem - C - Codeforces 给定一个整数数组a1,a2,...,an。 如果可以从a中删除一些元素得到b,则称数组b为a的子序列。 当且仅当对于每个i(1≤i≤k),bi是i的倍数时,数组b1,b2,...,bk被称为好。 在模109+7下找到a中好的子序列的数量。 如果两个子序列的包含数字的索引集合不同

    2024年02月02日
    浏览(30)
  • Python使用递归法对整数进行因数分解

    所谓因数分解,是指把一个整数变成其所有质因数相乘的形式,例如10=2*5, 39000=2*2*2*3*5*5*5*13。 from random import randint def factors(num, fac=[]):     #每次都从2开始查找因数     for i in range(2, int(num**0.5)+1):         #找到一个因数         if num%i == 0:             fac.append(i)        

    2023年04月23日
    浏览(36)
  • e[2333333, 23333333] 中有多少个正整数 可以被分解为 12 个质数相乘?

    任何一个大于 1 的正整数都能被分解为若干个质数相乘, 比如 28=2 times 2 times 728=2×2×7 被分解为了三个质数相乘。请问在区间 [2333333, 23333333] 中有多少个正整数 可以被分解为 12 个质数相乘? 答案提交 这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一

    2023年04月08日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包