# SMPLSUM - Editorial **URL:** \ **Category:** editorial\ **Tags:** easy, editorial, factorization, nov15\ **Created:** [November 14, 2015, 7:19pm UTC](https://discuss.codechef.com/t/smplsum-editorial/11875 "2015-11-14T19:19:20Z")\ **Posts on this page:** 11\ **Page:** 2
**Author:** ![xariniov9](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@xariniov9](https://discuss.codechef.com/u/xariniov9)\ **Post date:** [November 17, 2015, 11:30am UTC](https://discuss.codechef.com/t/smplsum-editorial/11875/21 "2015-11-17T11:30:18Z")
oops! I observed that, in this solution he freed the memory before returning, so freeing variable memory does not count in the final results? I always thought they calculate the total memory used on the runtime for entire execution and result displays the maximum memory required. ---
**Author:** ![xariniov9](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@xariniov9](https://discuss.codechef.com/u/xariniov9)\ **Post date:** [November 17, 2015, 2:15pm UTC](https://discuss.codechef.com/t/smplsum-editorial/11875/22 "2015-11-17T14:15:11Z")
Instead of finding primes, you could have found lowest prime factor of each number. [https://discuss.codechef.com/questions/76818/prime-factorization-of-large-numbers](https://discuss.codechef.com/questions/76818/prime-factorization-of-large-numbers) ---
**Author:** ![apptica](https://discuss.codechef.com/user_avatar/discuss.codechef.com/apptica/32/307283_2.png) [@apptica](https://discuss.codechef.com/u/apptica)\ **Post date:** [November 17, 2015, 4:28pm UTC](https://discuss.codechef.com/t/smplsum-editorial/11875/23 "2015-11-17T16:28:32Z")
I also applied sieve for 10000000 but i think the complexity is n log(log(n)) and it should work as it is less than 10^8 ---
**Author:** ![s1d\_3](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@s1d\_3](https://discuss.codechef.com/u/s1d_3)\ **Post date:** [November 17, 2015, 5:06pm UTC](https://discuss.codechef.com/t/smplsum-editorial/11875/24 "2015-11-17T17:06:07Z")
@bhishma - How did you create an array of 10^7 elements? I thought of this same thing, but dropped the idea as C++ doesn’t allow creation of int arrays of more than 2\*10^6 I think. ---
**Author:** ![bhishma](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@bhishma](https://discuss.codechef.com/u/bhishma)\ **Post date:** [November 17, 2015, 6:45pm UTC](https://discuss.codechef.com/t/smplsum-editorial/11875/25 "2015-11-17T18:45:31Z")
I coded in java , and as far as I know we could create arrays of size 10^8 without any issues. ---
**Author:** ![xellos0](https://discuss.codechef.com/user_avatar/discuss.codechef.com/xellos0/32/24644_2.png) [@xellos0](https://discuss.codechef.com/u/xellos0)\ **Post date:** [November 18, 2015, 3:55am UTC](https://discuss.codechef.com/t/smplsum-editorial/11875/26 "2015-11-18T03:55:15Z")
@s1d_3: Stack limit can kill static arrays. Did you actually try submitting a code with a vector\<\> of that size? ---
**Author:** ![arpit728](https://discuss.codechef.com/user_avatar/discuss.codechef.com/arpit728/32/4830_2.png) [@arpit728](https://discuss.codechef.com/u/arpit728)\ **Post date:** [December 12, 2015, 8:31am UTC](https://discuss.codechef.com/t/smplsum-editorial/11875/27 "2015-12-12T08:31:51Z")
@xellos0 Reply?? ---
**Author:** ![xariniov9](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@xariniov9](https://discuss.codechef.com/u/xariniov9)\ **Post date:** [December 13, 2015, 8:38pm UTC](https://discuss.codechef.com/t/smplsum-editorial/11875/28 "2015-12-13T20:38:54Z")
That equivalently means that the result for a number ‘n’ is equal to the product of the result of two numbers ‘n1’ and ‘n2’ iff gcd(n1, n2)=1 i.e. they are coprime. If n1 and n2 are further represented as the product of two coprime numbers, you eventually reach at the numbers that are “powers of a single prime”. Now the only task is “how to calculate the result for numbers, which are powers of a single prime?” This is fairly simple and can be done by summing the phi(d).d for every divisor d of that number. Have a look on this solution : [https://www.codechef.com/viewsolution/8767177](https://www.codechef.com/viewsolution/8767177) ---
**Author:** ![xariniov9](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@xariniov9](https://discuss.codechef.com/u/xariniov9)\ **Post date:** [December 16, 2015, 10:45am UTC](https://discuss.codechef.com/t/smplsum-editorial/11875/29 "2015-12-16T10:45:03Z")
The basic approach for any problem is to think of the possible solution and observing the patterns while keeping the constraints in the mind at the same time. When you get some approach, think about it and try to prove the correctness, if you’re not able to prove the correctness, try to find a counter example, if you’re not able to find one, never hesitate to implement the approach in long challenges. At the end, long challenge will teach you a lot. ---
**Author:** ![arpit728](https://discuss.codechef.com/user_avatar/discuss.codechef.com/arpit728/32/4830_2.png) [@arpit728](https://discuss.codechef.com/u/arpit728)\ **Post date:** [December 16, 2015, 11:30am UTC](https://discuss.codechef.com/t/smplsum-editorial/11875/30 "2015-12-16T11:30:07Z")
@xariniov9 Thanks,I understand how to calculate the answer.I am unable to arrive at the proof can you please simplify the proof. ---
**Author:** ![thefallenstar](https://discuss.codechef.com/user_avatar/discuss.codechef.com/thefallenstar/32/4173_2.png) [@thefallenstar](https://discuss.codechef.com/u/thefallenstar)\ **Post date:** [April 6, 2020, 8:38pm UTC](https://discuss.codechef.com/t/smplsum-editorial/11875/31 "2020-04-06T20:38:21Z")
You can actually use result 2 to come up with a faster solution which will basically compute the answer for all n in [1..n] in linear time. Since \sum d . \phi(d) is a multiplicative function, we can use the concept mentioned here [[Tutorial] Math note — linear sieve - Codeforces](https://codeforces.com/blog/entry/54090) My submission: [CodeChef: Practical coding for everyone](https://www.codechef.com/viewsolution/24962858) [Previous page](https://discuss.codechef.com/t/smplsum-editorial/11875.md?page=1)