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

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

10042 smith number wa>>>>

Post by ayeshapakhi » Thu Jul 06, 2006 2:50 pm

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:

Post by 898989 » Wed Aug 02, 2006 10:32 pm

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
If you need more about this Just ask
Sleep enough after death, it is the time to work.
Mostafa Saad

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Thu Aug 24, 2006 9:20 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
Bangladesh

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

Post by tan_Yui » Thu Aug 24, 2006 11:52 pm

Hi, Kallol.

http://online-judge.uva.es/board/viewto ... ight=10042
This thread will just help you.

Best regards.

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Fri Aug 25, 2006 9:56 pm

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 :lol:
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

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

Need some I/O

Post by marif » Wed Oct 04, 2006 9:01 am

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

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

WA... somebody plz help me out!!

Post by pradeepr » Tue May 29, 2007 4:17 pm

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...
please help me out..

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

Re: 10042 - Smith Numbers

Post by dplt » Thu May 22, 2008 6:58 pm

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
Location: University Of Dhaka,Bangladesh
Contact:

Re: 10042 - Smith Numbers

Post by Shafaet_du » Mon Oct 18, 2010 4:04 pm

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

Post by hwj1593 » Tue Jul 23, 2013 10:03 am

#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>>>>

Post by brianfry713 » Wed Jul 24, 2013 3:25 am

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

Post by hwj1593 » Thu Jul 25, 2013 9:36 am

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

Post by brianfry713 » Sat Jul 27, 2013 4:04 am

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

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 10042 - Smith Numbers

Post by mahade hasan » Wed Oct 30, 2013 5:27 pm

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

Post by brianfry713 » Thu Oct 31, 2013 10:20 pm

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!

Post Reply

Return to “Volume 100 (10000-10099)”