OJ Board

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.

A prime number is not a smith's number.
You don't check this point in your program

Hope this helps

Thans, Now I got Accepted!

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

try to use unsigned long

Dominik

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

Thanks.....

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

Thanks.....

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

Dominik

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.

i have solved prime factor but in this cases i got tle..
would you please help me with a faster algorithm..

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.

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

There won't be negative numbers inputted would there? I thought Smith numbers were only positive. So why would that matter?

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