## 10042 - Smith Numbers

Moderator: Board moderators

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

### 10042 smith number wa>>>>

hi..
pls help me finding the bug>>>
thanks for any help...

Code: Select all

``````#include <stdio.h>   //10042 Submit ###
#include <math.h>

#define U 47001
#define N 5000

bool tag[U];
long primes[N],c=0;

inline bool isprime(long n);
inline void seive(void);

void main()
{
long num,all[N],i,j,k,intg,real,sumd,sumpd,test,l;

seive();

scanf("%ld",&test);

for(k=0; k<test; k++)
{
scanf("%ld",&num);

for(l=num;   ; l++)
{
real=l;
sumd=0;
while( real !=0)
{
sumd+=real%10;
real =real/10;
}

i=0;
intg=l;
for(j=0; ; j++)
{
if( intg==1) break;
if( isprime(intg) )
{
all[i++]=intg;
break;
}
while( intg % primes[j] == 0)
{
all[i++]=primes[j];
intg/=primes[j];
}
}

sumpd=0;

for(j=0; j<i; j++)
{
intg=all[j];

while( intg!=0)
{
sumpd+=intg%10;
intg=intg/10;
}
}
if(sumd== sumpd)
{
printf("%ld\n",l);
break;
}
}
}
}

inline bool isprime(long n)
{
long i,temp;
if(n==1) return false;

if(n==2) return true;

if(n%2==0) return false;
temp=(long)sqrt(n);

for(i=0; primes[i]<=temp; i++) if(n % primes[i]==0) return false;

return true;
}

inline void seive(void)
{
long i,j,r;

for(i=2; i<U; i++) tag[i]=true;

primes[c++]=2;

for(i=3; i<U; i+=2)
{
if( tag[i])
{
primes[c++]=i;

if( (U/i) >= i)
{
r=i*2;
for(j=i*i; j<U; j+=r) tag[j]=false;
}
}
}
}

``````
thanks.

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:
I did not read your code carefully...But her is a good note
Most who get wrong answer assume smith number is a prime number
I think you do that

Note
No need for generating any primes...Just a function that try all i that less than or equal to its sqrt
Sleep enough after death, it is the time to work.

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
I am at my wits end what to do. I tried by all means but could not break the vicious cycle of WA from the online judge !!
here is my code:

Code: Select all

``````cut after ACC
``````
It passes all the inputs . I checked it with almost possible inputs and everytime it gives me the right answer. I dont know where it is going wrong . Is theke anyone to help me?
Last edited by Kallol on Fri Aug 25, 2006 9:57 pm, edited 1 time in total.
Syed Ishtiaque Ahmed Kallol
CSE,BUET

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am
Hi, Kallol.

http://online-judge.uva.es/board/viewto ... ight=10042

Best regards.

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
Thanx a lot.
I just missed out the case for 2.
I almost left trying that problem and wasted lots of my time for that silly mistake.Now I got ACCEPTED.
Thank u once again Syed Ishtiaque Ahmed Kallol
CSE,BUET

marif
New poster
Posts: 11
Joined: Sat Jun 24, 2006 11:42 am
Contact:

### Need some I/O

There are some inputs but no corresponding outputs. Pls someone post correct outputs.

New poster
Posts: 21
Joined: Fri May 25, 2007 11:52 am
Location: India

### WA... somebody plz help me out!!

this is the code...

#include<iostream>
#include<cstdlib>
#include<vector>
#include<cmath>
using namespace std;
int sum_digits(long num)
{
int sum=0;
while(num!=0)
{
sum+=num%10;
num/=10;
}
return sum;
}
int main()
{
vector<long> primes;
vector<int>primes_sum;
primes.push_back(2);
primes_sum.push_back(2);
long limit=(long)floor(sqrt(1000000000)),num,j;
int num_cases;
for(long i=3;i<=limit;i++)
{
bool flag=true;
int size=primes.size();
for (int j=0;j<size;j++)
{
if(i%primes[j]==0)
{
flag=false;
break;
}
}

if(flag)
{
primes.push_back(i);
primes_sum.push_back(sum_digits(i));
}

}
cin >>num_cases;
for(int k=0;k<num_cases;k++)
{
std::cin >>j;
j++;
while (1)
{
int total_count=0;
num=j;
int digits=sum_digits(num),prime_digits=0;
for(int i=0;i<primes.size()&&num!=1;i++)
{
int count=0;
while(num%primes==0)
{
count++;
num/=primes;
total_count++;
}
prime_digits+=primes_sum*count;
count=0;
}
if(num!=1)
{
prime_digits+=sum_digits(num);
total_count++;
}
if(digits==prime_digits && total_count>1 )
{
cout<<j<<'\n';
break;

}
else
j++;
}
}
return(0);
}

I tried out evrything....but couldnt find the mistake...

dplt
New poster
Posts: 4
Joined: Thu Feb 15, 2007 4:30 pm
Location: Indonesia
Contact:

### Re: 10042 - Smith Numbers

Anybody who still got WA should read these notes:
1. Prime numbers are NOT Smith numbers
2. Integer data type is ENOUGH, instead using unsigned or long long
3. Output for 1,000,000,000 is 1,000,000,165
4. Output for 1 is 4 !!!

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Contact:

### Re: 10042 - Smith Numbers

sample:

Code: Select all

``````10
123423
345332
456456
23
434535
999
234523
233232
45454
54645``````
output:

Code: Select all

``````123464
345343
456502
27
434542
1086
234562
233257
45495
54654``````

hwj1593
New poster
Posts: 2
Joined: Tue Jul 23, 2013 9:58 am

### 10042 smith number wa>>>>

#include <stdio.h>

unsigned Factorize(unsigned u);
int sumPosNumber(unsigned number);

int main()
{
unsigned number = 29716;
unsigned smith= 0;
unsigned result = 1;
unsigned max;

scanf("%ld",&max);
for(unsigned i=0;i<max;i++){
scanf("%ld",&number);
number++;
while(smith != result )
{
result = Factorize(number);
// printf("result = %ld\n",result);
if(result != 0){
smith = sumPosNumber(number);
// printf("smith = %ld\n",smith);
}
number++;
}
printf("%ld\n",number-1);
result = 0;
}
return 0;
}

unsigned Factorize(unsigned u)
{
unsigned init = u;
unsigned result = 0;
unsigned temp;

for(unsigned i = 2;i<u;)
{
if(u%i == 0)
{
temp = sumPosNumber(i);
//printf("%ld",temp);
result += temp;
if (u!=i)
{
// printf("*");
u /= i;
i = 2;
}
}else
i++;

}
if(init == u){

return 0;
}
// printf("%d\n",u);

temp = sumPosNumber(u);
return result+temp;
}

int sumPosNumber(unsigned number)
{
int smith = 0;
int temp;

while(1)
{
if(number == 0){
break;
}else{
temp = number%10;
smith += temp;
}

number = number/10;
}
return smith;
}

why ... wa?
i'm not good well english... sorry about ..

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10042 smith number wa>>>>

scanf and printf should use %u for unsigned, %ld is for a long.
Check input and AC output for thousands of problems on uDebug!

hwj1593
New poster
Posts: 2
Joined: Tue Jul 23, 2013 9:58 am

### Re: 10042 smith number wa>>>>

thanks to brianfry713 !! time limit t. t

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10042 smith number wa>>>>

Start by precomputing a list of primes.
Check input and AC output for thousands of problems on uDebug!

Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm

### Re: 10042 - Smith Numbers

Acc
Last edited by mahade hasan on Fri Nov 01, 2013 7:19 pm, edited 1 time in total.
we r surrounded by happiness
need eyes to feel it!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10042 - Smith Numbers

Try to speed up your Cal function. If you only want 10,000 primes you only need to check up to 104,729, not 100,000,000.
Check input and AC output for thousands of problems on uDebug!