# Identify Smith Numbers

# Identify Smith Numbers

edzvh + 2 comments Having spent 20 mins googling prime factorization algorithms I fail to see how this is an "easy" problem. Maybe I'm just being a thicko.

nebasuke + 1 comment Indeed, making this a 10 point easy warmup problem is really undervaluing the hardness of solving this, especially comparing to all of the other easy 20 point solutions.

Shafaet + 1 comment Well its not a hard or medium problem :). May be it should have 20 points, but not more than that.

chawlanmol + 0 comments [deleted]

bennattj + 1 comment Well a pretty simple/naive prime factorization algorithm works for the test cases. All you need to do is find the first factor (start testing with 2). The first number you find that works is guaranteed to be a prime number. Then keep dividing until the number is no longer divisible by that prime--keep the count (since you'll need that later). Then keep going until the number becomes 1.

Now I don't know whether or not you need the following "optimization", but I used it because I already had it from the Primitive Number problem. If the last number you end up with is a large prime, then you might needlessly test a bunch of numbers only to find out that there weren't any (i.e. it was prime). Use the fact that if two factors exist they will be on either side of the square root. So if the number you are currently testing, squares to something larger than the remaining number, then that number must be prime and you can quit and just add one instance of that large prime (rather than testing all of the numbers greater than the square root of that large prime--which will require substantially more testing than up to the square root).

pgmreddy + 0 comments About 10% is unclear on what you said. I din't do Primitive Number due to it's success rate (may be you are reffering to https://www.hackerrank.com/challenges/primitive-problem)

I did completely different way. Passed on 1st submission for all tests,but it took 2 hour to make it run, also because of out of memory problem. I did some other optimizations.

Definitely either not easy, or not 20 points. Following is 50, but took 1/2 the time. https://www.hackerrank.com/challenges/john-and-gcd-list/problem

Somehow points are not right for problems.

algaey + 1 comment Please check your test case answers 4937775 for example shows it is a Smith number but one of its prime factors is 65837!! how can this be a smith no. I'm pretty sure my program is correct so please check the answers to the test cases

YoungBlood + 1 comment "A Smith number is a composite number, the sum of whose digits is

`THE SUM OF THE DIGITS`

of its prime factors obtained as a result of prime factorization (excluding 1)." So when you add up the prime factors of 4937775 (which are 3, 5, 5 and 65837) you will add them like this:`3+5+5+6+5+8+3+7`

(which is equal to`4+9+3+7+7+7+5`

)algaey + 0 comments tnx a lot bro...got it working now

abhishek93131 + 0 comments my code with all test cases submitted

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static void main(String[] args) { Scanner in=new Scanner(System.in); long n=in.nextLong(); long digits=SUM1(n); long factors=SUM2(n); if(digits==factors) System.out.print("1"); else System.out.print("0"); /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ } public static long SUM1(long n) { long s=0; while(n!=0) { long rem=n%10; s=s+rem; long num=n/10; n=num; } return s; } public static long SUM2(long n) { long add=0; while(n%2==0) { add=add+2; n=n/2; } for(long j=3;j<=Math.sqrt(n);j=j+2) { while(n%j==0) { if(j>=10) { long p=j; while(p!=0) { long r=p%10; add=add+r; p=p/10; }} else { add=add+j; } n=n/j; } } if(n>1) { while(n!=0) { long r=n%10; add=add+r; n=n/10; } } return add; } }

gotRefill + 2 comments Wow. I got it, but this one being tagged as "easy" has to be a joke. :D

I'm real worried about the "hard" problems now, if this is "easy".

patheyshah + 1 comment Actually it was a pretty simple problem here the solution given by him is also bit complex a simpler solution is that just loop untill your number is not equal to 1. check this code out int m=n; int sum1=0; int sum2=0; while(m!=0) { sum1+=m%10; m=m/10; } m=n; while(m!=1) { for(int i=2;i<=m;i++) { if(m%i==0) { System.out.println(i); m=m/i; int k=i; while(k!=0) { sum2+=(k%10); k=k/10; } break; } } } System.out.println(sum1); System.out.println(sum2); if(sum1==sum2) return 1; else return 0;

pgmreddy + 0 comments May be pretty simple, you should try 100 rank in Math domain.

pgmreddy + 0 comments

asianfanfics68 + 0 comments Great article. I hope you will continue to have so many high quality articles to share with us. I believe many people will be surprised to read this article. thank you! fnaf

phamyenmta94 + 0 comments Great post,Thanks for providing us this great knowledge,Keep it up. girls go games

monicaphillipa + 0 comments I would like to say that I don't know if you need the next "optimization", but I use it because I got it from the original number. If the last number is the large prime number, you can try the group numbers unnecessarily to find it. I am professional seo services provider and I am aware with the search engine spider calculation that's why I suggested.

chetan_raikwar + 0 comments I wrote an easy to understand code :)

#******************************# # Author: chetan_raikwar # # Date: 18/03/2019 # #******************************# # primes up to 500 (sufficient to factorize max int value mostly) primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499] # returns sum of digits of n def digitSum(n): if n == 0: return 0 else: return (n % 10) + digitSum(n // 10) #******** main ********# n = int(input()) if n == 1: print('0') else: m = n sum1 = i = 0 while i < len(primes): if m % primes[i] == 0: m //= primes[i] sum1 += primes[i] else: i += 1 else: # remaining is prime if m > 1: sum1 += m # ultimate digit sum of both sums while sum1 > 9: sum1 = digitSum(sum1) sum2 = digitSum(n) while sum2 > 9: sum2 = digitSum(sum2) if sum1 == sum2: print('1') else: print('0')

dinhphuong569 + 0 comments great post. i like it. feeling great when reading your post .

suparna869713331 + 0 comments int solve(int n) { int sum,sumf,i; sum=sumOfdigits(n); sumf=sumOfdigitofFactors(n); if(sum==sumf){ return 1; } return 0; } int sumOfdigits(n) { int sum=0,r; while(n!=0){ r=n%10; sum=sum+r; n=n/10; } return sum; } int sumOfdigitofFactors(int n){ int i,sum,cnt=0; sum = 0 ;

while (n % 2 == 0) { sum=sum+2; n = n / 2; } for(i=3;i<=n;i=i+2){ while(n%i==0){ if(i>=10){ cnt = sumOfdigits(i); sum = sum + cnt; } else{ sum=sum+i; }

`n=n/i; }`

} return sum; }

Sort 54 Discussions, By:

Please Login in order to post a comment