\\[ 1+2+3+\u2026+n\\ \\ \\ =\\ \\ \\ \\frac{n\\left(n+1\\right)}{2} \\]<\/p>\n\n\n\n
\\[ 1^2+2^2+3^2+\u2026+n^2\\ \\ \\ =\\ \\ \\ \\frac{n\\left(n+1\\right)\\left(2n+1\\right)}{6} \\]<\/p>\n\n\n\n
\\[ 1^3+2^3+3^3+\u2026+n^3\\ \\ \\ =\\ \\ \\ \\left[\\frac{n\\left(n+1\\right)}{2}\\right]^2 \\]<\/p>\n\n\n\n
For an AP series, \\[ a_1+a_2+a_3+\u2026..+b\\ \\ =\\ \\ \\frac{1}{2}\\left(a+b\\right) \\]<\/p>\n\n\n\n
For a GP series, \\[ a+ak+ak^2+ak^3+\u2026..+b\\ \\ =\\ \\ \\frac{bk-a}{k-1} \\]<\/p>\n\n\n\n
For a Harmonic Series \\[ \\sum_{k=1}^n\\frac{1}{k} \\], the sum is always less than or equal to \\( 1+\\log_2n \\)<\/p>\n\n\n\n
\\[ \\Rightarrow 1+\\frac{1}{2}+\\frac{1}{3}+\\frac{1}{4}+\\frac{1}{5}+\\frac{1}{6}+\\frac{1}{7}+\\frac{1}{8}+\u2026. \\]<\/p>\n\n\n\n
\\[ \\le1+\\underline{\\frac{1}{2}+\\frac{1}{2}}+\\underline{\\frac{1}{4}+\\frac{1}{4}+\\frac{1}{4}+\\frac{1}{4}}+\\underline{\\frac{1}{8}+\u2026\u2026..} \\]<\/p>\n\n\n\n
Used to find all prime numbers from 1 to N with the help of a boolean array.<\/p>\n\n\n\n
Following is an in-efficient<\/mark> \\( O\\left(n^2\\right) \\) way to prepare the array:<\/p>\n\n\n\n Following is an optimised<\/mark> \\( O\\left(n\\log\\left(\\log n\\right)\\right) \\) version of above approach:<\/p>\n\n\n\n GCD of two numbers \\( a \\) and \\( b \\) is the greatest integer number which is a divisor of both \\( a \\) and \\( b \\). As an example, GCD of 6 and 10 is 2 because 2 is the greatest integer which can equally devide both 6 and 10. and GCD of 6 and 12 is 6 because 6 can equally devide both 6 as well as 12.<\/p>\n\n\n\n GCD is also called HCF (Highest common factor) or GCM (Greatest common measure)<\/p>\n\n\n\n <\/p>\n\n\n\n Let, \\( g \\) is GCD of \\( a \\) and \\( b \\)<\/p>\n\n\n\n \\( \\Rightarrow a=g\\cdot k_1 \\) and \\( b=g.k_2 \\)<\/p>\n\n\n\n \\( \\Rightarrow\\left(a+b\\right)=g\\left(k_1+k_2\\right) \\)<\/p>\n\n\n\n Which prooves that \\( g \\) is divisor of \\( \\left(a+b\\right) \\)<\/p>\n<\/div>\n<\/div>\n\n\n\n In addition to calculating just the GCD using euclidean algo as explained above in properties of GCD, the Extended<\/span> Euclidean algorithm also helps in finding the coefficients of B\u00e9zout’s identity \\( x \\) and \\( y \\). i.e., if \\( \\gcd\\left(a,b\\right)=d \\), then the extended euclidean helps in finding coefficients \\( x \\) and \\( y \\), such that \\( xa+yb=d \\).<\/p>\n\n\n\n The above equation is called B\u00e9zout’s identity. This equation is particularly usefull when \\( a \\) and \\( b \\) are co-primes, in that case, \\( xa+yb=1 \\) which implies that \\( x \\) is modular multiplicative inverse of \\( a \\) and \\( y \\) is modular multiplicative inverse of \\( b \\). Modular multiplicative inverse, for instance, has application in cryptography. <\/p>\n\n\n\nint<\/span> maxN =<\/span> 100<\/span>;<\/span>\nboolean<\/span> isPrime[<\/span>]<\/span> =<\/span> new<\/span> boolean<\/span>[<\/span>maxN +<\/span> 1<\/span>]<\/span>;<\/span>\nisPrime[<\/span>1<\/span>]<\/span> =<\/span> false<\/span>;<\/span>\nfor<\/span> (<\/span>int<\/span> i =<\/span> 2<\/span>;<\/span> i <=<\/span> maxN;<\/span> i++<\/span>)<\/span>\n for<\/span> (<\/span>int<\/span> j =<\/span> i *<\/span> 2<\/span>;<\/span> j <=<\/span> maxN;<\/span> j +=<\/span> i)<\/span> {<\/span>\n isPrime[<\/span>j]<\/span> =<\/span> false<\/span>;<\/span><\/pre>\n\n\n\nint<\/span> maxN =<\/span> 100<\/span>;<\/span>\nboolean<\/span> isPrime[<\/span>]<\/span> =<\/span> new<\/span> boolean<\/span>[<\/span>maxN +<\/span> 1<\/span>]<\/span>;<\/span>\nisPrime[<\/span>1<\/span>]<\/span> =<\/span> false<\/span>;<\/span>\nfor<\/span> (<\/span>int<\/span> i =<\/span> 2<\/span>;<\/span> i *<\/span> i <=<\/span> maxN;<\/span> i++<\/span>)<\/span>\n if<\/span> (<\/span>isPrime[<\/span>i]<\/span>)<\/span>\n for<\/span> (<\/span>int<\/span> j =<\/span> i *<\/span> i;<\/span> j <=<\/span> maxN;<\/span> j +=<\/span> i)<\/span> {<\/span>\n isPrime[<\/span>j]<\/span> =<\/span> false<\/span>;<\/span><\/pre>\n<\/div>\n<\/div>\n\n\n\nGCD (Greatest Common Devisor)<\/h3>\n\n\n\n
Properties of GCD<\/h4>\n\n\n\n
\n
public<\/span> int<\/span> gcd(<\/span>int<\/span> a, int<\/span> b)<\/span> {<\/span>\n if<\/span> (<\/span>b ==<\/span> 0<\/span>)<\/span> return<\/span> a;<\/span>\n \/\/notice that the position of a % b, b are swapped, this is to ensure<\/span>\n \/\/that the right argument is always smaller than left argument<\/span>\n \/\/if not swapped, seperate condition checks have to be implemented which<\/span>\n \/\/will check the larger and smaller numbers to calculate the remainder<\/span>\n return<\/span> gcd(<\/span>b, a %<\/span> b)<\/span>;<\/span>\n }<\/span><\/pre>\n<\/div>\n<\/div>\n\n\n\n\n
\n
\n
From wikipedia<\/h5>\n\n\n\n
\n
\n
\n
Extended Euclidean algorithm<\/h4>\n\n\n\n