IA-32 machine code, 27 bytes
Hexdump:
60 33 db 8b f9 33 c0 92 43 50 f7 f3 85 d2 75 04
ab 93 ab 93 3b c3 5a 77 ec 61 c3
Source code (MS Visual Studio syntax):
pushad;
xor ebx, ebx;
mov edi, ecx;
myloop:
xor eax, eax;
xchg eax, edx;
inc ebx;
push eax;
div ebx;
test edx, edx;
jnz skip_output;
stosd;
xchg eax, ebx;
stosd;
xchg eax, ebx;
skip_output:
cmp eax, ebx;
pop edx;
ja myloop;
popad;
ret;
First parameter (ecx) is a pointer to output, second parameter (edx) is the number. It doesn't mark the end of output in any way; one should prefill the output array with zeros to find the end of the list.
A full C++ program that uses this code:
#include <cstdint>
#include <vector>
#include <iostream>
#include <sstream>
__declspec(naked) void _fastcall doit(uint32_t* d, uint32_t n) {
_asm {
pushad;
xor ebx, ebx;
mov edi, ecx;
myloop:
xor eax, eax;
xchg eax, edx;
inc ebx;
push eax;
div ebx;
test edx, edx;
jnz skip_output;
stosd;
xchg eax, ebx;
stosd;
xchg eax, ebx;
skip_output:
cmp eax, ebx;
pop edx;
ja myloop;
popad;
ret;
}
}
int main(int argc, char* argv[]) {
uint32_t n;
std::stringstream(argv[1]) >> n;
std::vector<uint32_t> list(2 * sqrt(n) + 3); // c++ initializes with zeros
doit(list.data(), n);
for (auto i = list.begin(); *i; ++i)
std::cout << *i << '\n';
}
The output has some glitches, even though it follows the spec (no need for sorting; no need for uniqueness).
Input: 69
Output:
69
1
23
3
The divisors are in pairs.
Input: 100
Output:
100
1
50
2
25
4
20
5
10
10
For perfect squares, the last divisor is output twice (it's a pair with itself).
Input: 30
Output:
30
1
15
2
10
3
6
5
5
6
If the input is close to a perfect square, the last pair is output twice. It's because of the order of checks in the loop: first, it checks for "remainder = 0" and outputs, and only then it checks for "quotient < divisor" to exit the loop.
You probably mean divisor, not factor. And I guess you want to have a time complexity of
O(sqrt(n)). – flawr – 2016-05-01T08:40:21.973What is the difference between divisor and factor? – Leaky Nun – 2016-05-01T08:42:13.280
We talk about factors of e.g. a number, if the product of these results in the original number again, but the divisors are usually the numbers that divide said number without remainder. – flawr – 2016-05-01T08:44:11.647
@flawr Updated accordingly. – Leaky Nun – 2016-05-01T08:45:21.203
I suppose built-ins for divisors themselves are also disallowed. :P (Might want mention that explicitly.) – Martin Ender – 2016-05-01T10:22:01.903
@MartinBüttner As long as their complexity does not exceed O(sqrt(n)). – Leaky Nun – 2016-05-01T12:09:43.273
2Should have more examples.
99 (1 3 9 11 33 99)– Brad Gilbert b2gills – 2016-05-01T18:53:59.513