Perfect totient numbers: Difference between revisions
Content deleted Content added
→{{header|Go}}: Added much quicker version using Euler's product formula. |
Added C implementation |
||
Line 11:
<br><br>
=={{header|C}}==
Calculates as many number of perfect Totient numbers as entered on the command line, 40 numbers take around 320 seconds on a Core i5 with 8 GB RAM.
<lang C>
/*Abhishek Ghosh, 8th December 2018*/
#include<stdlib.h>
#include<stdio.h>
long totient(long n){
long tot = n,i;
for(i=2;i*i<=n;i+=2){
if(n%i==0){
while(n%i==0)
n/=i;
tot-=tot/i;
}
if(i==2)
i=1;
}
if(n>1)
tot-=tot/n;
return tot;
}
long* perfectTotients(long n){
long *ptList = (long*)malloc(n*sizeof(long)), m,count=0,sum,tot;
for(m=1;count<n;m++){
tot = m;
sum = 0;
while(tot != 1){
tot = totient(tot);
sum += tot;
}
if(sum == m)
ptList[count++] = m;
}
return ptList;
}
long main(long argC, char* argV[])
{
long *ptList,i,n;
if(argC!=2)
printf("Usage : %s <number of perfect Totient numbers required>",argV[0]);
else{
n = atoi(argV[1]);
ptList = perfectTotients(n);
printf("The first %d perfect Totient numbers are : \n[",n);
for(i=0;i<n;i++)
printf(" %d,",ptList[i]);
printf("\b]");
}
return 0;
}
</lang>
Output for multiple runs, a is the default executable file name produced by GCC
<pre>
C:\rossetaCode>a 10
The first 10 perfect Totient numbers are :
[ 3, 9, 15, 27, 39, 81, 111, 183, 243, 255]
C:\rossetaCode>a 20
The first 20 perfect Totient numbers are :
[ 3, 9, 15, 27, 39, 81, 111, 183, 243, 255, 327, 363, 471, 729, 2187, 2199, 3063, 4359, 4375, 5571]
C:\rossetaCode>a 30
The first 30 perfect Totient numbers are :
[ 3, 9, 15, 27, 39, 81, 111, 183, 243, 255, 327, 363, 471, 729, 2187, 2199, 3063, 4359, 4375, 5571, 6561, 8751, 15723, 19683, 36759, 46791, 59049, 65535, 140103, 177147]
C:\rossetaCode>a 40
The first 40 perfect Totient numbers are :
[ 3, 9, 15, 27, 39, 81, 111, 183, 243, 255, 327, 363, 471, 729, 2187, 2199, 3063, 4359, 4375, 5571, 6561, 8751, 15723, 19683, 36759, 46791, 59049, 65535, 140103, 177147, 208191, 441027, 531441, 1594323, 4190263, 4782969, 9056583, 14348907, 43046721, 57395631]
</pre>
=={{header|Go}}==
<lang go>package main
| |||