10042  Smith Numbers
Moderator: Board moderators

 Experienced poster
 Posts: 192
 Joined: Sat Nov 30, 2002 5:14 am
10042  Smith Numbers
I can't figure out why my program still got wring answer ?, If someone have any time, please tell me what's wrong with this code :
[[/code][/cpp][size=18][/size]
#include <stdio.h>
#include <string.h>
#include <math.h>
#define MAX 100000
#define MAXCHAR 1000
int smith, sum_smith,
prime[MAX], np=0,
ct_fact;
void gen_prime() {
int i,j,flag=1;
prime[np++] = 2; prime[np++] = 3; prime[np++] = 5;
for (i=7; np<10000; i+=2) {
flag = 1;
if (i%2) {
for (j=3; j<=sqrt(i); j+=2) {
if (!(i%j)) {
flag = 0;
break;
}
}
}
if (flag) prime[np++] = i;
}
}
int count_number(int number) {
int count=0, i;
char temp[MAXCHAR];
sprintf (temp, "%u", number);
for (i=0; i<strlen(temp); i++)
count += (temp[i]48);
return (count);
}
int count_factor(int number) {
int k,count=0;
for (k=0; k<np; k++) {
while (!(number%prime[k])) {
number /= prime[k];
count += count_number(prime[k]);
}
}
if (number > 1)
count += count_number(number);
return (count);
}
void process() {
int j;
for (j=smith; ; j++) {
sum_smith = count_number(j);
ct_fact = count_factor(j);
if (ct_fact == sum_smith) {
printf ("%d\n", j);
break;
}
}
}
int main () {
int n, i;
gen_prime();
scanf ("%d", &n);
for (i=1; i<=n; i++) {
scanf ("%d", &smith);
process();
}
return 0;
}
Thanks.
[[/code][/cpp][size=18][/size]
#include <stdio.h>
#include <string.h>
#include <math.h>
#define MAX 100000
#define MAXCHAR 1000
int smith, sum_smith,
prime[MAX], np=0,
ct_fact;
void gen_prime() {
int i,j,flag=1;
prime[np++] = 2; prime[np++] = 3; prime[np++] = 5;
for (i=7; np<10000; i+=2) {
flag = 1;
if (i%2) {
for (j=3; j<=sqrt(i); j+=2) {
if (!(i%j)) {
flag = 0;
break;
}
}
}
if (flag) prime[np++] = i;
}
}
int count_number(int number) {
int count=0, i;
char temp[MAXCHAR];
sprintf (temp, "%u", number);
for (i=0; i<strlen(temp); i++)
count += (temp[i]48);
return (count);
}
int count_factor(int number) {
int k,count=0;
for (k=0; k<np; k++) {
while (!(number%prime[k])) {
number /= prime[k];
count += count_number(prime[k]);
}
}
if (number > 1)
count += count_number(number);
return (count);
}
void process() {
int j;
for (j=smith; ; j++) {
sum_smith = count_number(j);
ct_fact = count_factor(j);
if (ct_fact == sum_smith) {
printf ("%d\n", j);
break;
}
}
}
int main () {
int n, i;
gen_prime();
scanf ("%d", &n);
for (i=1; i<=n; i++) {
scanf ("%d", &smith);
process();
}
return 0;
}
Thanks.

 New poster
 Posts: 16
 Joined: Fri Oct 11, 2002 11:03 pm
 Location: France

 Experienced poster
 Posts: 192
 Joined: Sat Nov 30, 2002 5:14 am

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
for this problem you just check sum of digit number, with sum of digit for all prime factor that number. for prime factor you can use algo for P583(prime facktor). if they are not same you check the next number. if you get number which they produce the same sum that's a smith number. but if the number is prime this is not a smith number.
this is my algo:
1. I put 10000 prime number in array.
2. after input I check the number prime or not.
3. if prime add input with one, and back to step 2.
4. if not, I sum all digit of input.
5. I check prime number and sum digit of prime number at the same time.
6. for step 5 I use same algo when I solve p583.
7. if(sum of digit input == sum of digit all prime number) out from loop, else back to step 2 until you add the input with one.
I think only this my algo. to sum digit I only divide the number with 10, until I modulus the number with 10. I sum the number of modulus.
maybe this will be help you, GOOD LUCK.
1. I put 10000 prime number in array.
2. after input I check the number prime or not.
3. if prime add input with one, and back to step 2.
4. if not, I sum all digit of input.
5. I check prime number and sum digit of prime number at the same time.
6. for step 5 I use same algo when I solve p583.
7. if(sum of digit input == sum of digit all prime number) out from loop, else back to step 2 until you add the input with one.
I think only this my algo. to sum digit I only divide the number with 10, until I modulus the number with 10. I sum the number of modulus.
maybe this will be help you, GOOD LUCK.

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
i've done this problem in the same way as Hisoka ....
My only one mistake (first time) was that I don't use unsigned, but signed int
Dominik
My only one mistake (first time) was that I don't use unsigned, but signed int
Dominik
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)