10042 - Smith Numbers

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10042 - Smith Numbers

Post by Red Scorpion » Sat Nov 30, 2002 5:32 am

:P 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

Post by Bistromath » Wed Dec 04, 2002 9:15 am

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

Post by Red Scorpion » Thu Dec 12, 2002 6:47 am

Thans, Now I got Accepted!

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

10042

Post by Hisoka » Fri Mar 07, 2003 4:52 pm

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 :x

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

Post by Dominik Michniewski » Fri Mar 07, 2003 5:07 pm

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

Post by Hisoka » Fri Mar 07, 2003 5:20 pm

I give special thanks to you dominick. with your hint I got AC now.
I'm very tired with this problem before......

Thanks..... :D

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

Post by Hisoka » Fri Mar 07, 2003 5:24 pm

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:

Post by Dominik Michniewski » Mon Mar 10, 2003 8:49 am

BTW. If you was read earlier thread about this problem, you could read the same ;-))

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:

Post by anupam » Mon Mar 17, 2003 3:17 pm

what is the algorithm before it??
help dominik..
--nb:
according to eor sugg..
i got ac anagram2
--thanks boss..
--anupam
:oops: :oops:
"Everything should be made simple, but not always simpler"

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

Post by Hisoka » Mon Mar 17, 2003 8:16 pm

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. :wink:

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Tue Mar 18, 2003 6:02 am

i have solved prime factor but in this cases i got tle..
would you please help me with a faster algorithm..
"Everything should be made simple, but not always simpler"

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

Post by Hisoka » Tue Mar 18, 2003 4:09 pm

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. :wink:

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

Post by Dominik Michniewski » Wed Mar 19, 2003 9:02 am

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

Post by kate » Wed May 28, 2003 9:45 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

Post by subbu » Fri May 30, 2003 12:56 am

it would matter when the actual answer falls out of range
for a signed int but stays in range of an unsigned int....

Post Reply

Return to “Volume 100 (10000-10099)”