Page 2 of 6

### 10042

Posted: 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]

Posted: 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]

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

Posted: 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!

Posted: Tue Aug 03, 2004 3:39 am
my AC program output
22
27
58
4937775
4937818
1000000165
31639

Posted: Tue Aug 03, 2004 3:47 am
I use int and get AC.

Posted: Thu Aug 12, 2004 1:12 pm
Thanks jackie,

my program has been accepted!

### 10042 Runtime Error??

Posted: 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]

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

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

### 10042 GET WA WHY

Posted: 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]

### 10042, smith number and WA

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

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);

}

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

### ?

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

Posted: 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... )

thanks!!!