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]
10042 - Smith Numbers
Moderator: Board moderators
[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]
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
So perhaps this should be the corresponding output:Wilansky decided later that a (simple and unsophisticated) prime number is not worth being a Smith number and he excluded them from the definition.
4937775
4997814
5445476
4648833
4898031
5789901
9554636
8545667
7564550
8798870
6787920
5789722
6465870
4875214
10000426
8889039
7777786
6666699
5555592
4444569
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
Is it
or
or
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!
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
Code: Select all
22
27
58
4937775
4937818
1000000165
31639
Code: Select all
4937775
4937775
4937775
4937775
4937818
1000000165
4937775
Code: Select all
4937818
4937818
4937818
4937818
4937818
1000000165
4937818
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!
10042 Runtime Error??
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]
[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]
10042 GET WA WHY
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]
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
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);
}
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);
}
-
Raj Ariyan
- Learning poster
- Posts: 70
- Joined: Sat Feb 05, 2005 9:38 am
- Location: Gurukul
?
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.
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 ....
thanks, but i know this:
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!!!
and my output from this input:(that i find in another post)Wilansky decided later that a (simple and unsophisticated) prime number is not worth being a Smith number and he excluded them from the definition.
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!!!