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

devtools/2024/11/24 15:04:37/

蓝桥杯原题:将一个正整数分解质因数例如:输入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/devtools/136570.html

相关文章

软件世界中的超级bug有哪些?

软件世界中的超级bug有很多&#xff0c;以下是一些历史上著名的案例&#xff1a; 1. Mars Climate Orbiter 1998&#xff1a;由于代码中的一个简单错误&#xff0c;导致火星气候轨道器发送了错误的导航信号&#xff0c;最终导致任务失败&#xff0c;损失超过1800万美元。 2. M…

鸿蒙开发:ForEach中为什么键值生成函数很重要

前言 在列表组件使用的时候&#xff0c;如List、Grid、WaterFlow等&#xff0c;循环渲染时都会使用到ForEach或者LazyForEach&#xff0c;当然了&#xff0c;也有单独使用的场景&#xff0c;如下&#xff0c;一个很简单的列表组件使用&#xff0c;这种使用方式&#xff0c;在官…

接上一主题,C++14中如何设计类似于std::any,使集合在C++中与Python一样支持任意数据?

这篇文章的重点是C多态的应用&#xff0c;但是如果你是C新手&#xff0c; 你需要了解以下C知识&#xff1a; 类 构造函数 拷贝构造函数 虚拟函数 纯虚拟函数 析构函数 类的继承 运算符重写 模板类 模板参数 数组 数组的传递 指针与动态内存分配 Python&#xff1a; s …

躺平成长-腾讯云数据库(又消失了一次)

开源竞争&#xff1a; 当你无法彻底掌握技术的时候&#xff0c;你就开源这个技术&#xff0c;形成更多的技术依赖&#xff0c;你会说 这不就是在砸罐子吗&#xff1f;一个行业里面总会有人砸罐子的&#xff0c;你不如先砸罐子&#xff0c;还能听个响声。 数据库的里面清洁的数据…

代码随想录算法训练营day 45|动态规划08

买卖股票的最佳时机1 之前贪心算法有提到过&#xff0c;我们算正区间的总和&#xff0c;只要是正区间就加入总和 dp[i][0]表示第i天持有该股票的最大收益&#xff0c;dp[i][1]表示第i天不持有该股票的最大收益 class Solution { public:int maxProfit(vector<int>&…

uniapp接入BMapGL百度地图

下面代码兼容安卓APP和H5 百度地图官网&#xff1a;控制台 | 百度地图开放平台 应用类别选择《浏览器端》 /utils/map.js 需要设置你自己的key export function myBMapGL1() {return new Promise(function(resolve, reject) {if (typeof window.initMyBMapGL1 function) {r…

【STL】12.unordered_set与unordered_map的模拟实现

一、源码及框架分析 SGI-STL30版本源代码中没有unordered_map和unordered_set&#xff0c;SGI-STL30版本是C11之前的STL版本&#xff0c;这两个容器是C11之后才更新的。但是SGI-STL30实现了哈希表&#xff0c;只容器的名字是hash_map和hash_set&#xff0c;他是作为非标准的容…

【数据结构OJ】【图论】货币套汇(图路径)

题目描述 套汇是指利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的同种货币。例如&#xff0c;假定1 美元可以买0.7 英镑&#xff0c;1 英镑可以买9.5 法郎&#xff0c;1法郎可以买到0.16美元。通过货币兑换&#xff0c;一个商人可以从1 美元开始买入&#xff0…