+ 2

What is the best(fast) way to get all divisors of a number?

23rd Mar 2017, 9:15 AM
Oleg Kupriianov
Oleg Kupriianov - avatar
3 Respostas
+ 1
from functools import reduce def factors(n): # get factors and their counts factors = {} nn = n i = 2 while i*i <= nn: while nn % i == 0: if not i in factors: factors[i] = 0 factors[i] += 1 nn //= i i += 1 if nn > 1: factors[nn] = 1 return factors def divisorGen(n): factors = list(factorsGen(n)) nfactors = len(factors) f = [0] * nfactors while True: yield reduce(lambda x, y: x*y, [factors[x][0]**f[x] for x in range(nfactors)], 1) i = 0 while True: f[i] += 1 if f[i] <= factors[i][1]: break f[i] = 0 i += 1 if i >= nfactors: return def factorsGen(n): for k,v in factors(n).items(): yield k,v s = int(input()) print('Divisors of number {}, is {}'.format(s, list(divisorGen(s))))
4th Jun 2017, 5:29 AM
Oleg Kupriianov
Oleg Kupriianov - avatar
0
#include <vector> #include <iostream> using namespace std; int main() { vector<int> tab; int num; cin>>num; for(int i = 0; i<=num; i++) { if (num%i == 0) { tab.push_back(i); } } system("pause>nul"); return 0; } You can check if it's working, because I wrote this code on train, so I couldn't check myself ^^ tab holds divisors
23rd Mar 2017, 10:13 AM
Jakub Stasiak
Jakub Stasiak - avatar
0
A simple answer in python would be looping all numbers, def divisor(num): return [i for i in range(1,num+1) if not num%i] print(divisor(60)) for faster algorithm, you should update the maximum number of your loop. def divisor(num_max, counter=1): if counter < num_max: if num%counter == 0: return [counter, int(num/counter)] + divisor(int(num/counter), counter+1) else: return divisor(num_max, counter+1) else: return [] print(divisor(60))
24th Mar 2017, 3:11 AM
Moataz El-Ibiary
Moataz El-Ibiary - avatar