Divisors of a natural number: Difference between revisions
Line 52: | Line 52: | ||
for (i=1 ; i<=16;i++) |
for (i=1 ; i<=16;i++) |
||
{ |
{ |
||
divisors(pow(2,i |
divisors(pow(2,i-1)); |
||
} |
} |
||
divisors(pow(2,31 |
divisors(pow(2,31-1)); |
||
return 0; |
return 0; |
||
}</lang> |
}</lang> |
||
Line 60: | Line 60: | ||
{{out}} |
{{out}} |
||
<pre>divisors(1) = [1] |
<pre>divisors(1) = [1] |
||
divisors( |
divisors(2) = [1,2] |
||
divisors( |
divisors(4) = [1,2,4] |
||
divisors( |
divisors(8) = [1,2,4,8] |
||
divisors( |
divisors(16) = [1,2,4,8,16] |
||
divisors( |
divisors(32) = [1,2,4,8,16,32] |
||
divisors( |
divisors(64) = [1,2,4,8,16,32,64] |
||
divisors( |
divisors(128) = [1,2,4,8,16,32,64,128] |
||
divisors( |
divisors(256) = [1,2,4,8,16,32,64,128,256] |
||
divisors( |
divisors(512) = [1,2,4,8,16,32,64,128,256,512] |
||
divisors( |
divisors(1024) = [1,2,4,8,16,32,64,128,256,512,1024] |
||
divisors( |
divisors(2048) = [1,2,4,8,16,32,64,128,256,512,1024,2048] |
||
divisors( |
divisors(4096) = [1,2,4,8,16,32,64,128,256,512,1024,2048,4096] |
||
divisors( |
divisors(8192) = [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192] |
||
divisors( |
divisors(16384) = [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384] |
||
divisors( |
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] |
|||
divisors(2147483647) = [1,2147483647]</pre> |
|||
</pre> |
|||
=={{header|C++}}== |
=={{header|C++}}== |
Revision as of 05:27, 14 April 2013
Create a program to generate all the divisors of a given 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
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>
- Output:
divisors of 1 = [1] divisors of 3 = [1,3] divisors of 7 = [1,7] divisors of 15 = [1,3,5,15] divisors of 31 = [1,31] divisors of 63 = [1,3,7,9,21,63] divisors of 127 = [1,127] divisors of 255 = [1,3,5,15,17,51,85,255] divisors of 511 = [1,7,73,511] divisors of 1023 = [1,3,11,31,33,93,341,1023] divisors of 2047 = [1,23,89,2047] divisors of 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 of 8191 = [1,8191] divisors of 16383 = [1,3,43,127,129,381,5461,16383] divisors of 32767 = [1,7,31,151,217,1057,4681,32767] divisors of 65535 = [1,3,5,15,17,51,85,255,257,771,1285,3855,4369,13107,21845,65535]
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>
- Output:
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]
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>
- Output:
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]
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>
- Output:
divisors of 1 = [1] divisors of 3 = [1,3] divisors of 7 = [1,7] divisors of 15 = [1,3,5,15] divisors of 31 = [1,31] divisors of 63 = [1,3,7,9,21,63] divisors of 127 = [1,127] divisors of 255 = [1,3,5,15,17,51,85,255] divisors of 511 = [1,7,73,511] divisors of 1023 = [1,3,11,31,33,93,341,1023] divisors of 2047 = [1,23,89,2047] divisors of 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 of 8191 = [1,8191] divisors of 16383 = [1,3,43,127,129,381,5461,16383] divisors of 32767 = [1,7,31,151,217,1057,4681,32767] divisors of 65535 = [1,3,5,15,17,51,85,255,257,771,1285,3855,4369,13107,21845,65535] divisors of 2147483647 = [1,2147483647]
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>
- Output:
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]