0%

较大的正整数因子

大概每日一题-较大的正整数的因子

今天的题

题目描述

求正整数n(<2 000 000 001)的所有因子

输入

一个小于 2 000 000 001 的正整数

输出

按从小到大的顺序输出这个整数的所有因子,不包含1和它本身
每个因子占一行

做题思路1:

遍历0到sqrt(n)的每一个数, 判断是否是n的因子, 如果是, 就存起来, 之后遍历存起来的数, 输出一对因子中的另一个.

伪代码:

输入n
循环i从2sqrt(n):
    如果n % i == 0:
        输出i
        data[count++] = i
循环i从count-10:
    如果data[i]!=sqrt(n):
        输出n/data[i]

伪代码2

循环i从2sqrt(n)-1:
    如果n%i==0:
        输出i
如果(int)(sqrt(n))*(int)(sqrt(n)) == n
    意味着n是完全平方数, sqrt(n)也是一个因子
    输出sqrt(n)
循环i从sqrt(n)-1到i
    如果n%i==0:
        输出n/i

后者相较前者省略了一个数组.

欢迎关注我的其它发布渠道