## 10042 - Smith Numbers

Moderator: Board moderators

Red Scorpion
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.

Bistromath
New poster
Posts: 16
Joined: Fri Oct 11, 2002 11:03 pm
Location: France
A prime number is not a smith's number.
You don't check this point in your program

Hope this helps

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
Thans, Now I got Accepted!

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

### 10042

I always got WA for this problem and I don't know where my mistake. can you help me to give me spesial I/O?

Thanks

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
try to use unsigned long

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)

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia
I give special thanks to you dominick. with your hint I got AC now.
I'm very tired with this problem before......

Thanks.....

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia
I give special thanks to you dominick. with your hint I got AC now.
I'm very tired with this problem before......

Thanks.....

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

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)

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
what is the algorithm before it??
help dominik..
--nb:
according to eor sugg..
i got ac anagram2
--thanks boss..
--anupam
"Everything should be made simple, but not always simpler"

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia
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.

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
i have solved prime factor but in this cases i got tle..
"Everything should be made simple, but not always simpler"

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia
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.

Dominik Michniewski
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
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)

kate
New poster
Posts: 11
Joined: Thu May 22, 2003 9:37 pm
There won't be negative numbers inputted would there? I thought Smith numbers were only positive. So why would that matter?

subbu
New poster
Posts: 28
Joined: Fri May 30, 2003 12:47 am
it would matter when the actual answer falls out of range
for a signed int but stays in range of an unsigned int....