Divisors of a natural number: Difference between revisions

From Rosetta Code
Content added Content deleted
m (redirect to: Factors_of_an_integer)
 
(10 intermediate revisions by 3 users not shown)
Line 1: Line 1:
#REDIRECT [[Factors_of_an_integer]]
{{draft task}}
Create a program to generate all the [[wp:Divisor|divisors]] of a given [[wp:Natural number|natural number]].

Use it to generate and show here all the divisors of the numbers 2**(n-1) for n in the (inclusive) range [1, 16] and also for n = 31

=={{header|C}}==
<lang c>// Implemented by Arjun Sunel

#include<stdio.h>
#include<math.h>
int divisors(int n)
{
int i, j;
printf("divisors(%d) = [",n);
for (i=1;i<n;i++)
{
if (n%i==0)
printf("%d,",i);
}
printf("%d]\n",i);
}

int main()
{
int n,i;
for (i=1 ; i<=16;i++)
{
divisors(pow(2,i)-1);
}
divisors(pow(2,31)-1);
return 0;
}</lang>

{{out}}
<pre>divisors(1) = [1]
divisors(3) = [1,3]
divisors(7) = [1,7]
divisors(15) = [1,3,5,15]
divisors(31) = [1,31]
divisors(63) = [1,3,7,9,21,63]
divisors(127) = [1,127]
divisors(255) = [1,3,5,15,17,51,85,255]
divisors(511) = [1,7,73,511]
divisors(1023) = [1,3,11,31,33,93,341,1023]
divisors(2047) = [1,23,89,2047]
divisors(4095) = [1,3,5,7,9,13,15,21,35,39,45,63,65,91,105,117,195,273,315,455,585,819,1365,4095]
divisors(8191) = [1,8191]
divisors(16383) = [1,3,43,127,129,381,5461,16383]
divisors(32767) = [1,7,31,151,217,1057,4681,32767]
divisors(65535) = [1,3,5,15,17,51,85,255,257,771,1285,3855,4369,13107,21845,65535]
divisors(2147483647) = [1,2147483647]</pre>

=={{header|C++}}==
<lang cpp>// Implemented by Arjun Sunel
#include<iostream>
#include<cmath>
using namespace std;

int divisors(int n)
{
int i, j;
cout<<"divisors("<<n<<") = [";
for (i=1;i<n;i++)
{
if (n%i==0)
cout <<i<<",";
}
cout<<n<<"]"<<endl;
}
int main()
{
int n,i;
for (i=1 ; i<=16;i++)
{
divisors(pow(2,i)-1);
}
divisors(pow(2,31)-1);
return 0;
}
</lang>
{{out}}
<pre>divisors(1) = [1]
divisors(3) = [1,3]
divisors(7) = [1,7]
divisors(15) = [1,3,5,15]
divisors(31) = [1,31]
divisors(63) = [1,3,7,9,21,63]
divisors(127) = [1,127]
divisors(255) = [1,3,5,15,17,51,85,255]
divisors(511) = [1,7,73,511]
divisors(1023) = [1,3,11,31,33,93,341,1023]
divisors(2047) = [1,23,89,2047]
divisors(4095) = [1,3,5,7,9,13,15,21,35,39,45,63,65,91,105,117,195,273,315,455,585,819,1365,4095]
divisors(8191) = [1,8191]
divisors(16383) = [1,3,43,127,129,381,5461,16383]
divisors(32767) = [1,7,31,151,217,1057,4681,32767]
divisors(65535) = [1,3,5,15,17,51,85,255,257,771,1285,3855,4369,13107,21845,65535]
divisors(2147483647) = [1,2147483647]
</pre>


=={{header|Python}}==
<lang python>import math
from operator import mul
from itertools import product
from functools import reduce


def fac(n):
'''\
return the prime factors for n
>>> fac(600)
[5, 5, 3, 2, 2, 2]
>>> fac(1000)
[5, 5, 5, 2, 2, 2]
>>>
'''
step = lambda x: 1 + x*4 - (x//2)*2
maxq = int(math.floor(math.sqrt(n)))
d = 1
q = n % 2 == 0 and 2 or 3
while q <= maxq and n % q != 0:
q = step(d)
d += 1
res = []
if q <= maxq:
res.extend(fac(n//q))
res.extend(fac(q))
else: res=[n]
return res

def fact(n):
'''\
return the prime factors and their multiplicities for n
>>> fact(600)
[(2, 3), (3, 1), (5, 2)]
>>> fact(1000)
[(2, 3), (5, 3)]
>>>
'''
res = fac(n)
return [(c, res.count(c)) for c in set(res)]

def divisors(n):
factors = fact(n) # [(primefactor, multiplicity), ...]
primes, maxpowers = zip(*factors)
powerranges = (range(m+1) for m in maxpowers)
powers = product(*powerranges)
return (
reduce(mul,
(prime**power for prime, power in zip(primes, powergroup)),
1)
for powergroup in powers)
if __name__ == '__main__':
for n in list(range(1,17)) + [31]:
tocalc = 2**n - 1
print("divisors(%s) = %s" % (tocalc, sorted(divisors(tocalc))))</lang>
{{out}}
<pre>divisors(1) = [1, 1]
divisors(3) = [1, 3]
divisors(7) = [1, 7]
divisors(15) = [1, 3, 5, 15]
divisors(31) = [1, 31]
divisors(63) = [1, 3, 7, 9, 21, 63]
divisors(127) = [1, 127]
divisors(255) = [1, 3, 5, 15, 17, 51, 85, 255]
divisors(511) = [1, 7, 73, 511]
divisors(1023) = [1, 3, 11, 31, 33, 93, 341, 1023]
divisors(2047) = [1, 23, 89, 2047]
divisors(4095) = [1, 3, 5, 7, 9, 13, 15, 21, 35, 39, 45, 63, 65, 91, 105, 117, 195, 273, 315, 455, 585, 819, 1365, 4095]
divisors(8191) = [1, 8191]
divisors(16383) = [1, 3, 43, 127, 129, 381, 5461, 16383]
divisors(32767) = [1, 7, 31, 151, 217, 1057, 4681, 32767]
divisors(65535) = [1, 3, 5, 15, 17, 51, 85, 255, 257, 771, 1285, 3855, 4369, 13107, 21845, 65535]
divisors(2147483647) = [1, 2147483647]</pre>

Latest revision as of 17:16, 15 April 2013

Redirect to:

Retrieved from "https://rosettacode.org/wiki/Divisors_of_a_natural_number?oldid=227936"