较大的正整数因子

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

今天的题

题目描述

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从2sqrt(n):
如果n % i == 0:
输出i
data[count++] = i
循环i从count-10:
如果data[i]!=sqrt(n):
输出n/data[i]

伪代码2

1
2
3
4
5
6
7
8
9
循环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

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