较大的正整数因子

发表于 分类于 本文字数： 271 阅读时长 ≈ 1 分钟

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

今天的题

题目描述

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

输入

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

输出

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

做题思路1:

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

伪代码:

1
2
3
4
5
6
7
8
输入n
循环i从2到sqrt(n):
    如果n % i == 0:
        输出i
        data[count++] = i
循环i从count-1到0:
    如果data[i]!=sqrt(n):
        输出n/data[i]

伪代码2

1
2
3
4
5
6
7
8
9
循环i从2到sqrt(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

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