Divisors of a natural number: Difference between revisions
Line 6:
=={{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
</lang>
{{out}}
<pre>divisors of 1 = [1]
divisors of
divisors of
divisors of
divisors of
divisors of
divisors of
divisors of
divisors of
divisors of
divisors of
divisors of
divisors of
divisors of
divisors of
divisors of
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>
|
Revision as of 05:36, 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 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]
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(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]
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 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]
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]