蓝桥杯某C语言算法题解决方案(质因数分解)

ops/2024/11/25 22:55:54/

蓝桥杯原题:将一个正整数分解质因数例如:输入90,打印出90 = 2 * 3 * 3 * 5。


声明:该题目是否为蓝桥杯原题未知,我是从CSDN上面查到的,仅对该题目进行解决。

这个题与我之前发表过的一些关于检验一个数字是否为素数(质数)的项目相关性极大,如果我们要对一个数字进行质因数分解,首先我们要直到它可能会有哪些质因数。我们必须意识到,如果一个数字是它的因数,那么这个数字一定小于它。因此,它的质因数也一定会小于它。

这就给了我们突破口,首先我们要找到一些“候选素数(Candidates)”,也就是只要这些数字是素数,并且比我们需要检验的数字小,那么它们就有可能是它的质因数,也就是我们所属的候选素数。

单单找到这些素数还不行,我们还需要把他们存储起来以备后面检验它们是否是“真质因数(True prime factors)”

我必须提示大家,我这次写的项目并非最简单的方法,事实上,我们可以不用数组保存这些候选素数,而是直接在每个素数被找到之后立刻进行判断并且输出,这样会更简单一些。但是我这次不会给你展示这种方法,我展示的是使用了数组的方法,之后我会给出我提到的这个更好的方案,然而这次,我们要解释这个比较容易理解的方案

下面我们展示完整的代码:

//从2开始第500个素数是3571,因此本程序的arr_store最大储存3571,因此是有数据限制的。
// 基于以上原因,请不要尝试过大的数字。
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
void judPrime(int put,int arr[],int* y) {int a = put - 1; int trial = 0;for (a = put - 1; a > 0; a--) {if ((put % a == 0)&&(a!=1)) {trial++;}else if (a == 1) {}}if (trial == 0) {arr[*y] = put;*y=*y+1;}
}
int main()
{int input = 0; int judge = 0;int x = 2; int arr_store[500] = { 0 };int y = 0; int* py = &y;printf("请输入你要质数分解的数字:");scanf("%d", &input);for (x = 2; x < input; x++) {if (input % x == 0) {judge++;}}x = 2;if (judge == 0) {printf("输入的数字是素数,其质因数分解结果为:%d*1", input);}else {for (x = 2; x < input; x++) {judPrime(x, arr_store,py);}x = 0;while (arr_store[x] != 0) {if (input % arr_store[x] == 0) {printf("%d*", arr_store[x]);input /= arr_store[x];x++;}else {x++;}}printf("%d", input);}return 0;
}

由于我对数组arr_store的大小规定为500,因此我们最多能存下第500个质数,这就导致我们能判断的数字对象事实上是有限制的,一定会有一个比较大或者特殊的数超出我们能判断的范围,之后我会尝试给出不受这种限制的代码,虽然目前我还没有什么很好的头绪。


http://www.ppmy.cn/ops/136692.html

相关文章

[AutoSar]BSW_Diagnostic_007 BootLoader 跳转及APP OR boot response 实现

目录 关键词平台说明背景一、Process Jump to Bootloader二、相关函数和配置2.1 Dcm_GetProgConditions()2.2 Dcm_SetProgConditions() 三、如何实现在APP 还是BOOT 中对10 02服务响应3.1 配置3.2 code 四、报文五、小结 关键词 嵌入式、C语言、autosar、OS、BSW、UDS、diagno…

mybatis学习(一)

声明&#xff1a;该内容来源于动力节点&#xff0c;本人在学习mybatis过程中参考该内容&#xff0c;并自己做了部分笔记&#xff0c;但个人觉得本人做的笔记不如动力节点做的好&#xff0c;故使用动力节点的笔记作为后续mybatis的复习。 一、MyBatis概述 1.1 框架 在文献中看…

HBU算法设计与分析 贪心算法

1.最优会场调度 #include <bits/stdc.h> using namespace std; const int N1e55; typedef pair<int,int> PII; PII p[N]; priority_queue<int,vector<int>,greater<int>> q; //最小堆 存储最早结束的会场的结束时间 int n; //其实这个题可以理…

OpenAI震撼发布:桌面版ChatGPT,Windows macOS双平台AI编程体验!

【雪球导读】 「OpenAI推出ChatGPT桌面端」 OpenAI重磅推出ChatGPT桌面端&#xff0c;全面支持Windows和macOS系统&#xff01;这款新工具为用户在日常生活和工作中提供了前所未有的无缝交互体验。对于那些依赖桌面端进行开发工作的专业人士来说&#xff0c;这一更新带来了令人…

iOS屏幕共享技术实践

一、 背景 iOS应用中实现屏幕共享功能&#xff0c;允许用户在视频通话或互动直播中将屏幕内容以视频的方式分享给其他的观众&#xff0c;以增强互动体验&#xff0c;提高沟通效率。这种功能在视频会议、在线教育和游戏直播等场景中非常有用。 视频会议场景中&#xff0c;屏幕共…

网络安全的学习方向和路线是怎么样的?

最近有同学问我&#xff0c;网络安全的学习路线是怎么样的&#xff1f; 废话不多说&#xff0c;先上一张图镇楼&#xff0c;看看网络安全有哪些方向&#xff0c;它们之间有什么关系和区别&#xff0c;各自需要学习哪些东西。 在这个圈子技术门类中&#xff0c;工作岗位主要有以…

mysql约束和高级sql

约束 MySQL中的约束用于定义表中数据的规则&#xff0c;以确保数据的准确性和可靠性。以下是MySQL中常用的一些约束类型及其概述&#xff1a; PRIMARY KEY&#xff08;主键&#xff09;&#xff1a;唯一标识表中每条记录的字段或字段组合&#xff0c;一个表中只能有一个主键。…

深度学习中的长短期记忆网络(LSTM)与自然语言处理

一、LSTM简介 长短期记忆网络&#xff08;Long Short-Term Memory&#xff0c;简称LSTM&#xff09;是一种特殊的循环神经网络&#xff08;RNN&#xff09;&#xff0c;专门用于解决标准RNN在处理长期依赖问题时容易出现的梯度消失或梯度爆炸等问题。 LSTM的核心结构&#xf…