华为机试每日一练--第七题: 进制转换

简介: 华为机试每日一练--第七题: 进制转换

练习题入口

问题描述

功能:输入一个正整数,按照从小到大的顺序输出它的所有质因子(重复的也要列举)(如180的质因子为2 2 3 3 5 )

数据范围: 1 \le n \le 2 \times 10^{9} + 14 \1≤n≤2×109+14

输入描述:

输入一个整数

输出描述:

按照从小到大的顺序输出它的所有质数的因子,以空格隔开。

7482557e0a17aa188b45d2d4444d59b1_watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5aiB5aiB5rKB5rKB,size_18,color_FFFFFF,t_70,g_se,x_16.png

解题分析

       首先科普一下什么是质数的因子

质因子(或质因数)在数论里是指能整除给定正整数的质数。根据算术基本定理,不考虑排列顺序的情况下,每个正整数都能够以唯一的方式表示成它的质因数的乘积。两个没有共同质因子的正整数称为互质。因为1没有质因子,1与任何正整数(包括1本身)都是互质。只有一个质因子的正整数为质数。


将一个正整数表示成质因数乘积的过程和得到的表示结果叫做质因数分解。显示质因数分解结果时,如果其中某个质因数出现了不止一次,可以用幂次的形式表示。例如360的质因数分解是:

57bbef9eb20af5d9718f8f32a35a88cb_watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5aiB5aiB5rKB5rKB,size_20,color_FFFFFF,t_70,g_se,x_16.png

其中的质因数2、3、5在360的质因数分解中的幂次分别是3,2,1。

简而言之就是求一个数的因数,而这个因数必须是质数。


下面该分析解题思路了,我们知道n是由它的所有质因数相乘所得,那如何判断n的质因数呢?


质因数都是n的因子,所以当n取模等于0时,这个数就是n的质因数!


那如何找到所有的质因数呢?循环!假如质因数为a,当每次循环找到a后,我们就把n/a赋值为n(为了避免重复查找a),一直循环到找不到质因数为止。


       这样大致流程就确定了,但是我们也要减少循环次数,我们不能真的循环a-b次,那样耗费的时间就太长了。


当b>sqrt(a)+1时,就说明a中已经没有质因数了,这时循环就能结束了!


for (b=2; b < a; b++)
  {
  if (b > sqrt(a) + 1)
  {
    b = a;
  }
  if (a % b == 0)
  {
    printf("%d ", b);
    a = a / b;
  }
  }

上述伪代码其实存在漏洞,大家能发现吗?


我们看下图就能看到,第第三次循环找到了“4”,而4确不是120的质因数,所以上述代码存在问题

cc3c8f21db0e6b30f3f5f1b6c351db82_watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5aiB5aiB5rKB5rKB,size_20,color_FFFFFF,t_70,g_se,x_16.png

4为2*2,就说明a中的质因数不唯一,有重复的,那我们可不可以在一次for循环中在添加一个while循环,一直挑选出所有与b相同的质因数。

for (b=2; b < a; b++)
  {
  if (b > sqrt(a) + 1)
  {
    b = a;
  }
  while (a % b == 0)
  {
    printf("%d ", b);
    a = a / b;
  }
  }

这样我们就能顺利找出重复的质因数了


代码实现

#include<stdio.h>
#include<math.h>
int main()
{
    int a, b, i = 0;
    scanf("%d", &a);
    for (b = 2; b <= a; b++)
    {
        if (b > sqrt(a) + 1) //最小质数因子必小于输入数字的平方根
        {
            b = a;
        }
        while (a % b == 0)
        {
            printf("%d ", b);
            a = a / b;
        }
    }
    return 0;
}

7085e24accead436ff770abb0fecbf97_watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5aiB5aiB5rKB5rKB,size_20,color_FFFFFF,t_70,g_se,x_16.png

相关文章
|
30天前
|
算法
刷题专栏(三):二进制求和
刷题专栏(三):二进制求和
42 0
|
7月前
|
Python
牛客刷题之数学基础-约数
牛客刷题之数学基础-约数
28 0
|
算法 C语言 C++
【C语言蓝桥杯每日一题】——等差数列
这道题,我用到了C语言中的qsort库函数,它是一种基于快排算法思想的排序函数。首先,想让大家认识一下qsort库函数的大概样子,和如何使用。
126 0
|
存储 算法 C语言
【C语言蓝桥杯每日一题】——数字三角形
数字三角形🙌 题目描述 上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,你的任务就是找到最大的和。路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数。此外,向左下走的次数与向右下走的次数相差不能超过 1。
101 0
【C语言蓝桥杯每日一题】——数字三角形
|
Serverless 测试技术
华为机试每日一练--第五题: 进制转换
写出一个程序,接受一个十六进制的数,输出该数值的十进制表示。 数据范围:保证结果在 1≤n≤2^31−1
华为机试每日一练--第五题: 进制转换
|
机器学习/深度学习
华为机试每日一练--第六题: 蛇形矩阵
华为机试每日一练--第六题: 蛇形矩阵
华为机试每日一练--第六题: 蛇形矩阵
|
C语言
蓝桥杯---等差数列(C语言)
找出5个数中两数最小之差(假定公差)
130 0
蓝桥杯---等差数列(C语言)
华为机试每日一练--第九题: 字符串反转
华为机试每日一练--第九题: 字符串反转
华为机试每日一练--第九题: 字符串反转
华为机试每日一练--第八题: 取近似值
华为机试每日一练--第八题: 取近似值
华为机试每日一练--第八题: 取近似值
每日一题1055:进制转换
题目描述: 编程,输入一个10进制正整数,然后输出它所对应的八进制数。 样例输入:
82 0

热门文章

最新文章