From 46aedfc6d8c04f384266b2e9692cf0aee564f1e0 Mon Sep 17 00:00:00 2001 From: drbaggy Date: Thu, 7 Oct 2021 06:56:05 +0100 Subject: now in C - slightly different end condition --- challenge-133/james-smith/c/ch-2.c | 65 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 65 insertions(+) create mode 100644 challenge-133/james-smith/c/ch-2.c diff --git a/challenge-133/james-smith/c/ch-2.c b/challenge-133/james-smith/c/ch-2.c new file mode 100644 index 0000000000..0a9480e21e --- /dev/null +++ b/challenge-133/james-smith/c/ch-2.c @@ -0,0 +1,65 @@ +#include + +// Compute all Smith Numbers below MAX_N +#define MAX_N 1000000 +#define PFSIZE (MAX_N/2) +#define PSIZE 100000 // Have to guess this! + +// Set up arrays +int sum_pf[ PFSIZE+1 ], primes[ PSIZE ], prime_index = 0; + +// Compute sum of digits - unlike Perl we can't use split +// so we use repeated modulus/divide by 10.. + +int sum_digits(int n) { + int total = 0; + do { total += n%10; } while( n /= 10 ); + return total; +} + +// Get the sum of prime factors - +// as we build this in order we only need to find a +// factorisation then we just add together the +// digit sum of the two factors (Here for speed we +// know one will be prime. +// We go through all primes we have until prime^2 +// is greater than the number itself. +// +// To make the last bit easier IF we have a prime +// we return 0 as not composite... +// +// Note to save memory we only store the sum if +// n < MAX_N/2 as we won't need it again (can't +// be a factor of a larger number less than MAX_N + +int sum_prime_factors( int n ) { + int p; + for(int i=0; i< prime_index; i++ ) { + p = primes[i]; + if( !(n % p) ) { + if( n <= PFSIZE ) { + return sum_pf[n] = sum_pf[n/p] + sum_pf[p]; + } else { + return sum_pf[ n/p ] + sum_pf[ p ]; + } + } + if( n < p*p ) { break; } + } + if( n <= PFSIZE ) { + sum_pf[ n ] = sum_digits(n); + } + primes[ prime_index++ ] = n; + return 0; +} + +// Main is simple just loop and search, printing out +// Smith numbers +int main() { + int count = 0, n = 1; + while( n++ <= MAX_N ) { + if( sum_digits(n) == sum_prime_factors(n) ) { + printf( "%11d\n", n ); + } + } +} + -- cgit