Divisors of a natural number: Difference between revisions

From Rosetta Code
Content added Content deleted
(DO NOT Add to this draft task. It is a duplicate of another and will be replaced with a redirect (Just as soon as I remember how to do it or someone else obliges.)
m (redirect to: Factors_of_an_integer)
 
Line 1: Line 1:
#REDIRECT [[Factors_of_an_integer]]
{{draft task}}
'''DO NOT Add to this draft task. It is a duplicate of another and will be replaced with a redirect (Just as soon as I remember how to do it or someone else obliges.'''

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|Awk}}==
<lang awk># Implemented by Arjun Sunel
awk 'func divisors(n){printf "divisors of ";print n;printf " = [";for(j=1;j<n;j++){if(n%j==0){printf j;printf ","}};printf n;printf "]\n";}BEGIN{for(i=1;i<=16;i++)divisors((2^(i-1)) ); divisors(2^(31-1))}'
</lang>
{{out}}
<pre>divisors of 1 = [1]
divisors of 2 = [1,2]
divisors of 4 = [1,2,4]
divisors of 8 = [1,2,4,8]
divisors of 16 = [1,2,4,8,16]
divisors of 32 = [1,2,4,8,16,32]
divisors of 64 = [1,2,4,8,16,32,64]
divisors of 128 = [1,2,4,8,16,32,64,128]
divisors of 256 = [1,2,4,8,16,32,64,128,256]
divisors of 512 = [1,2,4,8,16,32,64,128,256,512]
divisors of 1024 = [1,2,4,8,16,32,64,128,256,512,1024]
divisors of 2048 = [1,2,4,8,16,32,64,128,256,512,1024,2048]
divisors of 4096 = [1,2,4,8,16,32,64,128,256,512,1024,2048,4096]
divisors of 8192 = [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192]
divisors of 16384 = [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384]
divisors of 32768 = [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768]
divisors of 1073741824 = [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824]
</pre>

=={{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(2) = [1,2]
divisors(4) = [1,2,4]
divisors(8) = [1,2,4,8]
divisors(16) = [1,2,4,8,16]
divisors(32) = [1,2,4,8,16,32]
divisors(64) = [1,2,4,8,16,32,64]
divisors(128) = [1,2,4,8,16,32,64,128]
divisors(256) = [1,2,4,8,16,32,64,128,256]
divisors(512) = [1,2,4,8,16,32,64,128,256,512]
divisors(1024) = [1,2,4,8,16,32,64,128,256,512,1024]
divisors(2048) = [1,2,4,8,16,32,64,128,256,512,1024,2048]
divisors(4096) = [1,2,4,8,16,32,64,128,256,512,1024,2048,4096]
divisors(8192) = [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192]
divisors(16384) = [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384]
divisors(32768) = [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768]
divisors(1073741824) = [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824]
</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(2) = [1,2]
divisors(4) = [1,2,4]
divisors(8) = [1,2,4,8]
divisors(16) = [1,2,4,8,16]
divisors(32) = [1,2,4,8,16,32]
divisors(64) = [1,2,4,8,16,32,64]
divisors(128) = [1,2,4,8,16,32,64,128]
divisors(256) = [1,2,4,8,16,32,64,128,256]
divisors(512) = [1,2,4,8,16,32,64,128,256,512]
divisors(1024) = [1,2,4,8,16,32,64,128,256,512,1024]
divisors(2048) = [1,2,4,8,16,32,64,128,256,512,1024,2048]
divisors(4096) = [1,2,4,8,16,32,64,128,256,512,1024,2048,4096]
divisors(8192) = [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192]
divisors(16384) = [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384]
divisors(32768) = [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768]
divisors(1073741824) = [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824]
</pre>

=={{header|Java}}==
<lang java>// Implemented by Arjun Sunel

public class divisors
{
static void ans(double a)
{
System.out.print("divisors of " +(int)a + " = [");
for(int i = 1; i < a; i = i+1)
{
if (a % i == 0)
{
System.out.print(i + ",");
}
}
System.out.print((int)a);
System.out.println("]");
}

public static void main(String args[])
{
for(int x = 1; x <= 16; x = x+1)
{
ans(Math.pow(2, x-1));
}
ans(Math.pow(2, 31-1));
}
}</lang>
{{out}}
<pre>divisors of 1 = [1]
divisors of 2 = [1,2]
divisors of 4 = [1,2,4]
divisors of 8 = [1,2,4,8]
divisors of 16 = [1,2,4,8,16]
divisors of 32 = [1,2,4,8,16,32]
divisors of 64 = [1,2,4,8,16,32,64]
divisors of 128 = [1,2,4,8,16,32,64,128]
divisors of 256 = [1,2,4,8,16,32,64,128,256]
divisors of 512 = [1,2,4,8,16,32,64,128,256,512]
divisors of 1024 = [1,2,4,8,16,32,64,128,256,512,1024]
divisors of 2048 = [1,2,4,8,16,32,64,128,256,512,1024,2048]
divisors of 4096 = [1,2,4,8,16,32,64,128,256,512,1024,2048,4096]
divisors of 8192 = [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192]
divisors of 16384 = [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384]
divisors of 32768 = [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768]
divisors of 1073741824 = [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824]
</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(2) = [1, 2]
divisors(4) = [1, 2, 4]
divisors(8) = [1, 2, 4, 8]
divisors(16) = [1, 2, 4, 8, 16]
divisors(32) = [1, 2, 4, 8, 16, 32]
divisors(64) = [1, 2, 4, 8, 16, 32, 64]
divisors(128) = [1, 2, 4, 8, 16, 32, 64, 128]
divisors(256) = [1, 2, 4, 8, 16, 32, 64, 128, 256]
divisors(512) = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512]
divisors(1024) = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]
divisors(2048) = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048]
divisors(4096) = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096]
divisors(8192) = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192]
divisors(16384) = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384]
divisors(32768) = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768]
divisors(1073741824) = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824]

</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"