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

problem
New poster
Posts: 27
Joined: Mon Nov 10, 2003 12:40 am

10042

Post by problem » Tue Nov 25, 2003 11:09 am

help me plz.give me the solution and check my problem why wa.
[c]


#include<stdio.h>
#include<string.h>
#include<math.h>
primefac(long int i);

main()
{
long int i,j,k,sum,t,sum1,r;
while(scanf("%ld",&i)!=EOF)
{
for(k=0;k<i;k++)
{
scanf("%ld",&j);
for(r=j+1;;r++)
{
t=r;
sum1=0;
while(t!=0)
{
sum1+=fmod(t,10);
t/=10;
}
sum=primefac(r); /*call function to factorize the number
and the summation of factorize number*/
if(sum1==sum) /*if sum1==sum exit smith number is found*/
{
printf("%ld",r);
break;
}
else
continue;
}
}
}
return 0;
}


primefac(long int x)
{
long int i,c,t,sum=0,p,v;
c=x;
while((c%2)==0&&c>2)
{
sum=sum+2;
c=c/2;
}

i=3;
t=sqrt(c)+1;

while(i<=sqrt(c)+1)
{
if((c%i)==0)
{
v=i;
while(v!=0)
{
p=fmod(v,10);
sum=sum+p;
v=v/10;
}
c=c/i;
}

else
i=i+2;
}
if(c>1)
{
while(c!=0)
{
p=fmod(c,10);
sum=sum+p;
c=c/10;
}
}
return sum;
}
[\c]

bayzid
New poster
Posts: 7
Joined: Sun Sep 14, 2003 8:09 am
Location: bangladesh
Contact:

Post by bayzid » Wed Dec 10, 2003 12:10 pm

[c]
Firstly sum up all the digit of the number then sum up the factorizing
number.if sum of each digit is equal to the sum of factorizing number
then the number is called smith number.

sample input:
-------------

20
4937774
4997775
5445454
4648787
4897987
5789798
9554564
8545644
7564545
8798798
6787878
5789721
6465788
4875211
9999999
8888888
7777777
6666666
5555555
4444444

sample output:
--------------

4937775
4997801
5445463
4648799
4897993
5789857
9554569
8545651
7564550
8798813
6787889
5789722
6465791
4875214
10000019
8888927
7777786
6666679
5555567
4444469
[\c]
arahman

rjhadley
Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States

Post by rjhadley » Fri Jan 02, 2004 10:03 pm

Wilansky decided later that a (simple and unsophisticated) prime number is not worth being a Smith number and he excluded them from the definition.
So perhaps this should be the corresponding output:
4937775
4997814
5445476
4648833
4898031
5789901
9554636
8545667
7564550
8798870
6787920
5789722
6465870
4875214
10000426
8889039
7777786
6666699
5555592
4444569

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

Post by WR » Mon Jun 07, 2004 10:29 am

Hi,

could it be that the problem statement is somewhat ambigous?

It says you're to find Smith numbers larger than 4937775 but the sample output is equal to 4937775.

In the output section it says "you are to compute the smallest Smith number which is larger than n...". I think when given a Smith number Red Scorpion's program outputs that very number.

In any case I need some help because I can't find the reason for WA.

What is the output for

Code: Select all

7
5
22
31
4937774
4937775
999999999
31601
Is it

Code: Select all

22
27
58
4937775
4937818
1000000165
31639
or

Code: Select all

4937775
4937775
4937775
4937775
4937818
1000000165
4937775
or

Code: Select all

4937818
4937818
4937818
4937818
4937818
1000000165
4937818
or are all wrong? Some test data would really help.

There is a sample (Dec. 03, Bayzid) but I don't think it's correct.
His output for 4997775 is 4997801, but that's a prime!

jackie
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am

Post by jackie » Tue Aug 03, 2004 3:39 am

my AC program output
22
27
58
4937775
4937818
1000000165
31639

jackie
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am

Post by jackie » Tue Aug 03, 2004 3:47 am

I use int and get AC.

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

Post by WR » Thu Aug 12, 2004 1:12 pm

Thanks jackie,

my program has been accepted!

oulongbin
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

10042 Runtime Error??

Post by oulongbin » Sun Sep 05, 2004 5:39 am

This is my code ,why it will RT??
[cpp]
#include <iostream>
using namespace std;
#include <cmath>
#include <cstdio>

bool b[20250000]={0};

void prime()
{
long i,j;
b[1]=1;
for(i=1;i<4500;i++)
if (b==0)
for(j=2;j<=20250000/i;j++)
b[i*j]=1;
}

int main()
{
long p[7000];
long i,j;
long n;
long x,t,pt,k;
prime();
j=-1;
for(i=2;;i++)
{
if(b==0)
p[++j]=i;
if(j==6999)
break;
}
cin>>n;
while(n--)
{
cin>>x;
for(i=x;;i++)
{
if(b==0){}
else
{
t=0;
pt=0;
x=i;
while(x!=0)
{
t+=x%10;
x/=10;
}
x=i;
for(j=0;;j++)
{
while(x%p[j]==0)
{
k=p[j];
while(k!=0)
{
pt+=k%10;
k/=10;
}
x/=p[j];
}
if(x==1)
break;
if(b[x]==0)
{
k=x;
while(k!=0)
{
pt+=k%10;
k/=10;
}
break;
}

}
if(t==pt)
break;
}

}
cout<<i<<endl;

}

return 0;
}

[/cpp]

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Sun Sep 05, 2004 7:17 am

[c]for(j=2;j<=20250000/i;j++)
b[i*j]=1;[/c]

i*j can become quite large...

oulongbin
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

Post by oulongbin » Sun Sep 05, 2004 10:01 am

thanx ,i have changed the value :
[cpp]
bool b[1000000]={0};
void prime()
{
int i,j;
b[1]=1;
for(i=1;i<1000;i++)
if (b==0)
for(j=2;j<=1000000/i;j++)
b[i*j]=1;
}
[/cpp]
but still got TLE.

User avatar
Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

10042 GET WA WHY

Post by Rocky » Thu Jan 06, 2005 6:30 am

HY I TRY TO SOLVE 10042 AND I GOT WA BUT I DO'NT KNOW WHY IT IS :)

HERE MY CODE :->

C++

#include <iostream.h>

#include <math.h>



#define max 100000



int main(void)

{

int a[max]={1,0},test;

long b,i,f,sum,digit_sum,smith;

long l,h,t,g=max,input;

t=(long)ceil(sqrt((double)g));

//scieve method

for(b=3;b<=t;b++)

{

f=b;

for(f=f+b;f*b<=max;f+=b)

{

a[f-1]=1;

}

}



cin>>test;

while(test)

{

cin>>smith;

if(smith==0)

break;

t = smith;

t++;

while(1)

{

input = t;

digit_sum = 0;

b=t;

f=0;

while(1)

{

f = b%10;

b = b/10;

digit_sum += f;

if(b==0)

break;

}



g = t;

sum = 0;

l=(long)ceil(sqrt((double)input));



for(i=2;i<=l;i++)

{

if(a[i-1]==0)

{

if(input==1)

{

sum += 1;

break;

}

while(1)

{

h = i;

if((input%h)==0&&(input>1))

{

b=h;

f=0;

while(1)

{

f = b%10;

b = b/10;

sum += f;

if(b==0)

break;

}

input=input/h;

}

else

break;

}

}

}

if(input>1)

{

if(t==input)
{

t++;
continue;
}

b=input;

f=0;

while(1)

{

f = b%10;

b = b/10;

sum += f;

if(b==0)

break;

}

}

if(sum==digit_sum)

{

cout<<t<<endl;

break;

}



else

{

t++;

continue;

}

}

test--;

}

return 0;

}

pls can any body help me....pls
[/code]

zprian
New poster
Posts: 13
Joined: Wed Mar 09, 2005 1:16 am

10042, smith number and WA

Post by zprian » Wed Mar 09, 2005 1:25 am

I always got WA for this problem and I don't know where my mistake.

where is the problem?????in my home goes well :cry:

using namespace std;
#include <iostream>
#include <list>
#include <cmath>

list<int> prim;
list<int> ::iterator itp=prim.begin();

inline void suma(unsigned int& s,int n)
{
while(n>0)
{
s+=n%10;
n=n/10;
}
}
inline bool esprim(int div)
{
for(int i=3;i*i<=div;i+=2)
if (div%i==0) return false;
return true;
}

inline void seguent_prim(int& div)
{ ++itp;
div=*itp;

}


void smith() {

unsigned long smith=0;
cin >> smith;
smith+=1;
list<unsigned int> fact;
bool trobat=false;
while(trobat==false){
fact.erase(fact.begin(),fact.end());
itp=prim.begin();
int div=2;
unsigned int sum=0;
unsigned int sum2=0;
unsigned long aux=0;
suma(sum,(int)smith);
aux=(int)smith;

while(div*div<=aux)
{
if(aux>=1e9){//greater
return;}
if (aux%div==0) {
fact.push_back(div);
aux=aux/div;

}
else{seguent_prim(div);}
}
if(aux!=1)fact.push_back(aux);

list<unsigned int> ::iterator itf=fact.begin();
while(itf!=fact.end())
{
suma(sum2,*itf);
++itf;
}
if(aux==(int)smith) smith+=1;
else if(sum2==sum){
cout << smith<<endl;
trobat=true;
}
else smith+=1;



}//end while trobat
}




int main(){
prim.push_back(2);
prim.push_back(3);
int i=0;
for(i=3;i<=50000;i+=2)
if(esprim(i)) prim.push_back(i);
int voltes=0;
cin >> voltes;
while(voltes>0){
voltes=voltes-1;
smith();
}
exit(0);

}

zprian
New poster
Posts: 13
Joined: Wed Mar 09, 2005 1:16 am

Post by zprian » Wed Mar 09, 2005 1:45 am

somebody can tell me what's the result?can tell me what I have to write to make the problem?

mercy

Raj Ariyan
Learning poster
Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul

?

Post by Raj Ariyan » Fri Mar 11, 2005 8:48 am

Hi,
The problem is basically easy problem. Read the following if you face any problem.

1. You have to find a smith number greater than the given input
2. A prime number is not a smith number. So escape calculation while u get a prime number
3. For each number that is not prime chcek digit sum of the number and the sum of the digit of its prime factor. if equal then print and stop if not then continue;
4. Before all this calculation precal all the prime within 105000.

Hope it helps. Good luck.
Some Love Stories Live Forever ....

zprian
New poster
Posts: 13
Joined: Wed Mar 09, 2005 1:16 am

Post by zprian » Fri Mar 11, 2005 8:26 pm

thanks, but i know this:
Wilansky decided later that a (simple and unsophisticated) prime number is not worth being a Smith number and he excluded them from the definition.
and my output from this input:(that i find in another post)

20
4937774
4997775
5445454
4648787
4897987
5789798
9554564
8545644
7564545
8798798
6787878
5789721
6465788
4875211
9999999
8888888
7777777
6666666
5555555
4444444

and my output:

4937775
4997814
5445476
4648833
4898031
5789901
9554636
8545667
7564550
8798870
6787920
5789722
6465870
4875214
10000426
8889039
7777786
6666699
5555592
4444569


and this no contains any prime number.( the post is http://acm.uva.es/board/viewtopic.php?t ... 05c6efe937 )

thanks Raj Ariyan, but...i still unknow where is my error :(

1.i try to find a 50000 fist prime numbers
2.i find the first smith number greater than a input, but i know that number is not prime because i find :

div-->is prime;
aux-->is "smith" or yours divisors, and i find:

while(div*div<=aux)--> this implies that div never been the same of aux.

(sorry of my english, is very poor... :( :oops: )

thanks!!!

Post Reply

Return to “Volume 100 (10000-10099)”