<?xml version='1.0' encoding='UTF-8'?><?xml-stylesheet href="http://www.blogger.com/styles/atom.css" type="text/css"?><feed xmlns='http://www.w3.org/2005/Atom' xmlns:openSearch='http://a9.com/-/spec/opensearchrss/1.0/' xmlns:blogger='http://schemas.google.com/blogger/2008' xmlns:georss='http://www.georss.org/georss' xmlns:gd="http://schemas.google.com/g/2005" xmlns:thr='http://purl.org/syndication/thread/1.0'><id>tag:blogger.com,1999:blog-5227790233130724908</id><updated>2024-09-01T01:23:42.265-07:00</updated><title type='text'>Viaje en Euler</title><subtitle type='html'>-My Journey on Project Euler.....</subtitle><link rel='http://schemas.google.com/g/2005#feed' type='application/atom+xml' href='http://my-approach-to-euler.blogspot.com/feeds/posts/default'/><link rel='self' type='application/atom+xml' href='http://www.blogger.com/feeds/5227790233130724908/posts/default?redirect=false'/><link rel='alternate' type='text/html' href='http://my-approach-to-euler.blogspot.com/'/><link rel='hub' href='http://pubsubhubbub.appspot.com/'/><author><name>Sabyasachi</name><uri>http://www.blogger.com/profile/01688296359470230325</uri><email>noreply@blogger.com</email><gd:image rel='http://schemas.google.com/g/2005#thumbnail' width='20' height='32' src='//blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgliPLdO3_DKKE4zePQbusFsYqmNhfoRzMKD9VilD375A5mc281P0nguOqrpj4qoJFvQm1dKlU4bXcaMwem0ZsySRNcTkVdroq5W4_Qqp3jTYIaK4skT0Ma68q_1CTL9g/s220/kgenesis.JPG'/></author><generator version='7.00' uri='http://www.blogger.com'>Blogger</generator><openSearch:totalResults>10</openSearch:totalResults><openSearch:startIndex>1</openSearch:startIndex><openSearch:itemsPerPage>25</openSearch:itemsPerPage><entry><id>tag:blogger.com,1999:blog-5227790233130724908.post-3779763757986267002</id><published>2010-10-07T09:18:00.001-07:00</published><updated>2010-10-07T10:03:59.795-07:00</updated><title type='text'>Problem 8: Sum of primes</title><content type='html'>Q:Find the sum of all the primes below two million.&lt;br /&gt;
&lt;br /&gt;
Sol:&lt;br /&gt;
&lt;br /&gt;
The logic used to solve the problem was the same as in problem 7 of finding the nth prime.&lt;br /&gt;
Code for the problem is also very similar,the small difference being finding the sum.&lt;br /&gt;
&lt;br /&gt;
#include&amp;lt;cstdio&amp;gt;&lt;br /&gt;
#include&amp;lt;cmath&amp;gt;&lt;br /&gt;
using namespace std;&lt;br /&gt;
&lt;br /&gt;
int main()&lt;br /&gt;
{&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp; int n;&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp; scanf(&quot;%d&quot;,&amp;amp;n);&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp; int arr[500000];&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp; int i=2;&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp; arr[0]=2;&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp; arr[1]=3;&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp; int k=1,j;&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp; long long sum=5;&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp; int nextprime,flag=0,c=1;&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp; nextprime=5;&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp; while(nextprime&amp;lt;n)&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp; {&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; flag=0;&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; for(j=0;((j &amp;lt; i)&amp;amp;&amp;amp;(arr[j]&amp;lt;=sqrt((double)nextprime)));j++)&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; {&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; if(nextprime%arr[j] == 0)&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; {&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; flag=1;&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; break;&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; }&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; }&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; if(flag==0)&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; {&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; arr[i]=nextprime;&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; if (arr[i]&amp;lt; n)&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; sum=sum+(long long)(arr[i]);&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; i++;&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; }&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; if(c==-1)&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; k++;&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; nextprime=6*k +c;&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; c=-c;&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp; }&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp; printf(&quot;%lld\n&quot;,sum);&lt;br /&gt;
&lt;/n)&gt;&lt;br /&gt;
}&lt;br /&gt;
&lt;br /&gt;
The program takes 2-3 seconds to execute for the value of n being two million.&lt;br /&gt;
&lt;br /&gt;
&lt;br /&gt;
&lt;br /&gt;
Please post your comments and doubts.&lt;br /&gt;
Suggestions for better algorithms are always welcome :)</content><link rel='replies' type='application/atom+xml' href='http://my-approach-to-euler.blogspot.com/feeds/3779763757986267002/comments/default' title='Post Comments'/><link rel='replies' type='text/html' href='http://my-approach-to-euler.blogspot.com/2010/10/problem-8-sum-of-primes.html#comment-form' title='0 Comments'/><link rel='edit' type='application/atom+xml' href='http://www.blogger.com/feeds/5227790233130724908/posts/default/3779763757986267002'/><link rel='self' type='application/atom+xml' href='http://www.blogger.com/feeds/5227790233130724908/posts/default/3779763757986267002'/><link rel='alternate' type='text/html' href='http://my-approach-to-euler.blogspot.com/2010/10/problem-8-sum-of-primes.html' title='Problem 8: Sum of primes'/><author><name>Sabyasachi</name><uri>http://www.blogger.com/profile/01688296359470230325</uri><email>noreply@blogger.com</email><gd:image rel='http://schemas.google.com/g/2005#thumbnail' width='20' height='32' src='//blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgliPLdO3_DKKE4zePQbusFsYqmNhfoRzMKD9VilD375A5mc281P0nguOqrpj4qoJFvQm1dKlU4bXcaMwem0ZsySRNcTkVdroq5W4_Qqp3jTYIaK4skT0Ma68q_1CTL9g/s220/kgenesis.JPG'/></author><thr:total>0</thr:total></entry><entry><id>tag:blogger.com,1999:blog-5227790233130724908.post-4086557877531880219</id><published>2010-02-04T09:30:00.000-08:00</published><updated>2010-02-06T00:29:37.145-08:00</updated><title type='text'>Problem 8: 1000 digit number</title><content type='html'>&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;Q.&amp;nbsp;&lt;/span&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;Find the greatest product of five consecutive digits in the 1000-digit number.&lt;/span&gt;&lt;/span&gt;&lt;br /&gt;
&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif; font-size: 16px;&quot;&gt;&lt;/span&gt;&lt;br /&gt;
&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif; font-size: 16px;&quot;&gt;&lt;div style=&quot;font-family: &#39;courier new&#39;; text-align: center;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;73167176531330624919225119674426574742355349194934&lt;br /&gt;
96983520312774506326239578318016984801869478851843&lt;br /&gt;
85861560789112949495459501737958331952853208805511&lt;br /&gt;
12540698747158523863050715693290963295227443043557&lt;br /&gt;
66896648950445244523161731856403098711121722383113&lt;br /&gt;
62229893423380308135336276614282806444486645238749&lt;br /&gt;
30358907296290491560440772390713810515859307960866&lt;br /&gt;
70172427121883998797908792274921901699720888093776&lt;br /&gt;
65727333001053367881220235421809751254540594752243&lt;br /&gt;
52584907711670556013604839586446706324415722155397&lt;br /&gt;
53697817977846174064955149290862569321978468622482&lt;br /&gt;
83972241375657056057490261407972968652414535100474&lt;br /&gt;
82166370484403199890008895243450658541227588666881&lt;br /&gt;
16427171479924442928230863465674813919123162824586&lt;br /&gt;
17866458359124566529476545682848912883142607690042&lt;br /&gt;
24219022671055626321111109370544217506941658960408&lt;br /&gt;
07198403850962455444362981230987879927244284909188&lt;br /&gt;
84580156166097919133875499200524063689912560717606&lt;br /&gt;
05886116467109405077541002256983155200055935729725&lt;br /&gt;
71636269561882670428252483600823257530420752963450&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;font-family: &#39;courier new&#39;; text-align: center;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;font-family: &#39;courier new&#39;; text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;Sol:&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;font-family: &#39;courier new&#39;; text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;The method adopted to solve the problem was creating a window of 5 digits, finding the product of numbers in it and then sliding the window over the whole of the number. Each time we advance one digit, a new digit is included in the window which is multiplied to earlier product and an old digit is discarded by which the product is divided. Thus we get a new product each time we slide the window. Finding maximum of the products is the answer.&amp;nbsp;&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;font-family: &#39;courier new&#39;; text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;This algorithm is simple, but trouble arises when there is a zero in between the number at some place. For those cases. in which zeroes appear, the 5 digit combinations are discarded i.e. they are not allowed to interfere with the window product. Thus awkward values are avoided.&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;font-family: &#39;courier new&#39;; text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;font-family: &#39;courier new&#39;; text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;The coding part is&amp;nbsp;&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;font-family: &#39;courier new&#39;; text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;font-family: &#39;courier new&#39;; text-align: left;&quot;&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: medium;&quot;&gt;#include &amp;lt;stdio.h&amp;gt;&lt;/span&gt;&lt;br /&gt;
&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: medium;&quot;&gt;#include&amp;nbsp;&amp;lt;stdlib.h&amp;gt;&lt;/span&gt;&lt;br /&gt;
&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: medium;&quot;&gt;#include&amp;nbsp;&amp;lt;string.h&amp;gt;&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;int main()&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;{&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp;int n,i,p=1,max,j;&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp;FILE *fp=fopen(&quot;input.txt&quot;,&quot;r&quot;);&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp;fscanf(fp,&quot;%d\n&quot;,&amp;amp;n);&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp;char *a=(char*)malloc(n * sizeof(char));&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp;a[0]=&#39;\0&#39;;&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp;char temp[100];&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp;while(fscanf(fp,&quot;%s&quot;,temp)!=EOF)&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp;{&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;strcat(a,temp);&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp;}&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp;int x=0;&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp;for(i=0;i&amp;lt;5;i++)&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp;{&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;if((a[x+i]-&#39;0&#39;)==0)&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;{&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; p=1;&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; x=x+i+1;&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; i=-1;&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;}&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;else&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;p=p * (a[x+i]-&#39;0&#39;);&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp;}&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp;max=p;&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp;int st=x+i;&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp;for(i=st;i&amp;lt;n;i++)&lt;n;i++)&gt;&lt;/n;i++)&gt;&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp;{&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;if((a[i]-&#39;0&#39;)==0)&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;{&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; p=1;&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; x=i+1;&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; for(j=0;(j&amp;lt;5)&amp;amp;&amp;amp;((x+j) &amp;lt; n);j++)&lt;n);j++)&gt;&lt;/n);j++)&gt;&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; {&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; if((a[x+j]-&#39;0&#39;)==0)&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;&lt;/span&gt;&lt;span class=&quot;Apple-tab-span&quot; style=&quot;white-space: pre;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;  &lt;/span&gt;&lt;/span&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt; &amp;nbsp; {&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &lt;/span&gt;&lt;span class=&quot;Apple-tab-span&quot; style=&quot;white-space: pre;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt; &lt;/span&gt;&lt;/span&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;p=1;&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &lt;/span&gt;&lt;span class=&quot;Apple-tab-span&quot; style=&quot;white-space: pre;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt; &lt;/span&gt;&lt;/span&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;x=x+j+1;&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &lt;/span&gt;&lt;span class=&quot;Apple-tab-span&quot; style=&quot;white-space: pre;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt; &lt;/span&gt;&lt;/span&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;j=-1;&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;&lt;/span&gt;&lt;span class=&quot;Apple-tab-span&quot; style=&quot;white-space: pre;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;  &lt;/span&gt;&lt;/span&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt; &amp;nbsp; }&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;&lt;/span&gt;&lt;span class=&quot;Apple-tab-span&quot; style=&quot;white-space: pre;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;  &lt;/span&gt;&lt;/span&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt; &amp;nbsp; else&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;&lt;/span&gt;&lt;span class=&quot;Apple-tab-span&quot; style=&quot;white-space: pre;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;  &lt;/span&gt;&lt;/span&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;p=p * (a[x+j]-&#39;0&#39;);&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;&amp;nbsp;&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; }&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; i=x+j-1; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;}&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;else&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;{&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; p=p/(a[i-5]-&#39;0&#39;);&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; p=p*(a[i]-&#39;0&#39;);&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;}&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;if(max&lt;p)&gt;&lt;/p)&gt;&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; max=p;&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp;}&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp;printf(&quot;\n%d\n&quot;,max);&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;}&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;In the program the input is taken from file input.txt, n denotes the number of digits in the number, the character array &#39;a&#39; is used to store the number. p denotes the product in the current window and max denotes the maximum product obtained yet.&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;As it can be seen, when zero occurs, the new product is obtained by finding a nearest window which doesn&#39;t have zero.&lt;/span&gt;&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div style=&quot;text-align: left;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-family: &#39;Trebuchet MS&#39;, Trebuchet, Verdana, sans-serif; font-size: 13px; line-height: 20px;&quot;&gt;&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;Please post your comments and doubts...&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;Suggestion for better algorithms are always welcome.....&lt;/span&gt;&lt;/span&gt;&lt;/div&gt;&lt;/span&gt;</content><link rel='replies' type='application/atom+xml' href='http://my-approach-to-euler.blogspot.com/feeds/4086557877531880219/comments/default' title='Post Comments'/><link rel='replies' type='text/html' href='http://my-approach-to-euler.blogspot.com/2010/02/problem-8-1000-digit-number.html#comment-form' title='0 Comments'/><link rel='edit' type='application/atom+xml' href='http://www.blogger.com/feeds/5227790233130724908/posts/default/4086557877531880219'/><link rel='self' type='application/atom+xml' href='http://www.blogger.com/feeds/5227790233130724908/posts/default/4086557877531880219'/><link rel='alternate' type='text/html' href='http://my-approach-to-euler.blogspot.com/2010/02/problem-8-1000-digit-number.html' title='Problem 8: 1000 digit number'/><author><name>Sabyasachi</name><uri>http://www.blogger.com/profile/01688296359470230325</uri><email>noreply@blogger.com</email><gd:image rel='http://schemas.google.com/g/2005#thumbnail' width='20' height='32' src='//blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgliPLdO3_DKKE4zePQbusFsYqmNhfoRzMKD9VilD375A5mc281P0nguOqrpj4qoJFvQm1dKlU4bXcaMwem0ZsySRNcTkVdroq5W4_Qqp3jTYIaK4skT0Ma68q_1CTL9g/s220/kgenesis.JPG'/></author><thr:total>0</thr:total></entry><entry><id>tag:blogger.com,1999:blog-5227790233130724908.post-5534592135105328947</id><published>2010-02-04T08:13:00.000-08:00</published><updated>2011-02-17T03:40:49.509-08:00</updated><title type='text'>Problem 7: Nth prime</title><content type='html'>&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;Q. What is the 10001st prime number?&lt;/span&gt;&lt;br /&gt;
&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;Sol:&lt;/span&gt;&lt;br /&gt;
&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;I got the idea to solve this problem from the algorithm &quot;Sieve of Eratosthenes&quot;&amp;nbsp; which finds the prime numbers upto a number. It just stores the number in an array selects one element of the array at a time in ascending order and eliminates the numbers in the array which come out to be multiple of the selected.&lt;/span&gt;&lt;br /&gt;
&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;If we start constructing an array starting with array values 2 and 3(the first two prime numbers) and then continue to incorporate the numbers in the array which are not multiple of previous values in array, we will always get a prime number in the array. Moreover it can be observed that any prime number can be expressed as (6x+1) or (6x-1). So, there is no need to check other numbers for divisiblity by numbers in array.&lt;/span&gt;&lt;br /&gt;
&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;&lt;br /&gt;
&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;Then, the algorithm is that we start from 2 and 3 as initial values in array, increment a variable so that it has always the value of the form 6x+1 or 6x-1 and check if not divisible by elements already present in the array. If not divisible by any one of them, the number is entered into the array.&lt;/span&gt;&lt;br /&gt;
&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;&lt;br /&gt;
&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;Now, comes the fun part........ coding&lt;/span&gt;&lt;br /&gt;
&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;&lt;br /&gt;
&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;#include&lt;/span&gt;&lt;cstdio&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&amp;lt; cstdio&amp;gt;&lt;br /&gt;
using namespace std; &lt;br /&gt;
&lt;br /&gt;
int main() &lt;br /&gt;
{ &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp; int n; &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp; scanf(&quot;%d&quot;,&amp;amp;n); &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp; int arr[100000]; &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp; int i=2; &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp; arr[0]=2; &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp; arr[1]=3; &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp; int k=1,j; &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp; int nextprime,flag=0,c=1; &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp; nextprime=5; &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp; while(i &amp;lt; n)&lt;/span&gt; &lt;n)&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp; { &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; flag=0; &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; for(j=0;((j &amp;lt; i)&amp;amp;&amp;amp;(arr[j]&amp;lt;=sqrt((double)nextprime)));j++)&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; { &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; if(nextprime%arr[j] == 0) &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; { &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; flag=1; &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; break; &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; } &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; } &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; if(flag==0) &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; { &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; arr[i]=nextprime; &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; i++; &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; } &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; if(c==-1)&lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; k++; &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; nextprime=6*k +c; &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; c=-c; &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp; } &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp; printf(&quot;%d\n&quot;,arr[n-1]); &lt;br /&gt;
}&lt;/span&gt;&lt;/i;j++)&gt;&lt;/n)&gt;&lt;/cstdio&gt;&lt;br /&gt;
&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;&lt;br /&gt;
&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;In the program, a variable k is is used to find the next element (which is 6k+1 or 6k-1) to be considered for position in the array.The element is checked for divisiblity and entered into array if not divisible by any of the numbers in the array....&lt;/span&gt;&lt;br /&gt;
&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;&lt;br /&gt;
&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-family: &#39;Trebuchet MS&#39;, Trebuchet, Verdana, sans-serif; line-height: 20px;&quot;&gt;&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;Please post your comments and doubts...&lt;/span&gt;&lt;/span&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;&lt;br /&gt;
&lt;/span&gt; &lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: small;&quot;&gt;Suggestion for better algorithms are always welcome.....&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;</content><link rel='replies' type='application/atom+xml' href='http://my-approach-to-euler.blogspot.com/feeds/5534592135105328947/comments/default' title='Post Comments'/><link rel='replies' type='text/html' href='http://my-approach-to-euler.blogspot.com/2010/02/problem-7-nth-prime.html#comment-form' title='0 Comments'/><link rel='edit' type='application/atom+xml' href='http://www.blogger.com/feeds/5227790233130724908/posts/default/5534592135105328947'/><link rel='self' type='application/atom+xml' href='http://www.blogger.com/feeds/5227790233130724908/posts/default/5534592135105328947'/><link rel='alternate' type='text/html' href='http://my-approach-to-euler.blogspot.com/2010/02/problem-7-nth-prime.html' title='Problem 7: Nth prime'/><author><name>Sabyasachi</name><uri>http://www.blogger.com/profile/01688296359470230325</uri><email>noreply@blogger.com</email><gd:image rel='http://schemas.google.com/g/2005#thumbnail' width='20' height='32' src='//blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgliPLdO3_DKKE4zePQbusFsYqmNhfoRzMKD9VilD375A5mc281P0nguOqrpj4qoJFvQm1dKlU4bXcaMwem0ZsySRNcTkVdroq5W4_Qqp3jTYIaK4skT0Ma68q_1CTL9g/s220/kgenesis.JPG'/></author><thr:total>0</thr:total></entry><entry><id>tag:blogger.com,1999:blog-5227790233130724908.post-1359541713265191448</id><published>2010-01-24T09:22:00.000-08:00</published><updated>2010-01-24T09:22:37.658-08:00</updated><title type='text'>Problem 6: Sum of squares or Square of sum !!!!</title><content type='html'>Q.&amp;nbsp;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;Sol:&amp;nbsp;&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;I think problem is also one of the easiest problems here.&amp;nbsp;&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;The problem can be easily solved through basic knowledge of Arithmetic-Geometric Progression....&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;We know that sum of squares of numbers from 1 to n is n(n+1)(2n+1)/6 and sum of the numbers from 1 to n is n(n+1)/2.&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;So, the result can be formulated into an expression&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;Difference= (n(n+1)/2) ^ 2 &amp;nbsp;- n(n+1)(2n+1)/6 = n(n+1)( 3(n^2) - n -2 ) / 12&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;Now all that remains is calculation....... &amp;nbsp;:D&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-family: &#39;Trebuchet MS&#39;, Trebuchet, Verdana, sans-serif; line-height: 20px;&quot;&gt;&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;Please post your comments...&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;Suggestion for better algorithms are always welcome.....&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;</content><link rel='replies' type='application/atom+xml' href='http://my-approach-to-euler.blogspot.com/feeds/1359541713265191448/comments/default' title='Post Comments'/><link rel='replies' type='text/html' href='http://my-approach-to-euler.blogspot.com/2010/01/problem-6-sum-of-squares-or-square-of.html#comment-form' title='0 Comments'/><link rel='edit' type='application/atom+xml' href='http://www.blogger.com/feeds/5227790233130724908/posts/default/1359541713265191448'/><link rel='self' type='application/atom+xml' href='http://www.blogger.com/feeds/5227790233130724908/posts/default/1359541713265191448'/><link rel='alternate' type='text/html' href='http://my-approach-to-euler.blogspot.com/2010/01/problem-6-sum-of-squares-or-square-of.html' title='Problem 6: Sum of squares or Square of sum !!!!'/><author><name>Sabyasachi</name><uri>http://www.blogger.com/profile/01688296359470230325</uri><email>noreply@blogger.com</email><gd:image rel='http://schemas.google.com/g/2005#thumbnail' width='20' height='32' src='//blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgliPLdO3_DKKE4zePQbusFsYqmNhfoRzMKD9VilD375A5mc281P0nguOqrpj4qoJFvQm1dKlU4bXcaMwem0ZsySRNcTkVdroq5W4_Qqp3jTYIaK4skT0Ma68q_1CTL9g/s220/kgenesis.JPG'/></author><thr:total>0</thr:total></entry><entry><id>tag:blogger.com,1999:blog-5227790233130724908.post-5461000710535729537</id><published>2010-01-24T09:03:00.000-08:00</published><updated>2010-01-24T09:04:41.580-08:00</updated><title type='text'>Problem 5:Least evenly divisible number</title><content type='html'>Q.&amp;nbsp;&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif; font-size: 16px;&quot;&gt;2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.What is the smallest number that is&amp;nbsp;&lt;dfn style=&quot;border-bottom-color: green; border-bottom-style: dotted; border-bottom-width: 1px; font-style: normal;&quot; title=&quot;divisible with no remainder&quot;&gt;evenly divisible&lt;/dfn&gt;&amp;nbsp;by all of the numbers from 1 to 20 ?&lt;/span&gt;&lt;br /&gt;
&lt;div&gt;&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;Sol:&lt;/span&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;It can be easily seen that the question is asking the LCM of the numbers.The problem can be solved without even resorting to algorithms.Just compute the prime factorization of numbers and multiply the highest power of each prime.&lt;/span&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;span style=&quot;-webkit-border-horizontal-spacing: 1px; -webkit-border-vertical-spacing: 1px;&quot;&gt;&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;20 = 2^2 * 5&lt;br /&gt;
19 = 19&lt;br /&gt;
18 = 2 * 3^2&lt;br /&gt;
17 = 17&lt;br /&gt;
16 = 2^4&lt;br /&gt;
15 = 3 * 5&lt;br /&gt;
14 = 2 * 7&lt;br /&gt;
13 = 13&lt;br /&gt;
11 = 11&amp;nbsp;&lt;/span&gt;&lt;/span&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;span style=&quot;-webkit-border-horizontal-spacing: 1px; -webkit-border-vertical-spacing: 1px;&quot;&gt;&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;Since all the lesser numbers have been included, they can be safely ignored..&lt;/span&gt;&lt;/span&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;span style=&quot;-webkit-border-horizontal-spacing: 1px; -webkit-border-vertical-spacing: 1px;&quot;&gt;&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;And&lt;/span&gt;&lt;/span&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;span style=&quot;-webkit-border-horizontal-spacing: 1px; -webkit-border-vertical-spacing: 1px;&quot;&gt;&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;lcm=&amp;nbsp;2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19&lt;/span&gt;&lt;/span&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;span style=&quot;-webkit-border-horizontal-spacing: 1px; -webkit-border-vertical-spacing: 1px;&quot;&gt;&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;&lt;/span&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;span style=&quot;-webkit-border-horizontal-spacing: 1px; -webkit-border-vertical-spacing: 1px;&quot;&gt;Now, the problem seems so simple, but what if we were to calculate the result for natural numbers from 1 to an arbitrary number(say &#39; n &#39;).&lt;/span&gt;&lt;/span&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;span style=&quot;-webkit-border-horizontal-spacing: 1px; -webkit-border-vertical-spacing: 1px;&quot;&gt;It can be observed that&amp;nbsp;&lt;/span&gt;&lt;/span&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;span style=&quot;-webkit-border-horizontal-spacing: 1px; -webkit-border-vertical-spacing: 1px;&quot;&gt;LCM(a,b,c,d)=LCM(b,c,LCM(a,d))&lt;/span&gt;&lt;/span&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;span style=&quot;-webkit-border-horizontal-spacing: 1px; -webkit-border-vertical-spacing: 1px;&quot;&gt;To implement it, we can run a loop from 2 to n-1 and at each step find the lcm of loop variable and the previous stage lcm.The lcm can be easily found by applying euclid&#39;s algorithm of finding GCD as&lt;/span&gt;&lt;/span&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;span style=&quot;-webkit-border-horizontal-spacing: 1px; -webkit-border-vertical-spacing: 1px;&quot;&gt;&amp;nbsp;LCM(a,b)=(a*b)/GCD(a,b).&lt;/span&gt;&lt;/span&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;span style=&quot;-webkit-border-horizontal-spacing: 1px; -webkit-border-vertical-spacing: 1px;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;&lt;/span&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;span style=&quot;-webkit-border-horizontal-spacing: 1px; -webkit-border-vertical-spacing: 1px;&quot;&gt;Now the coding part:&lt;/span&gt;&lt;/span&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;span style=&quot;-webkit-border-horizontal-spacing: 1px; -webkit-border-vertical-spacing: 1px;&quot;&gt;&lt;b&gt;&lt;br /&gt;
&lt;/b&gt;&lt;/span&gt;&lt;/span&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;span style=&quot;-webkit-border-horizontal-spacing: 1px; -webkit-border-vertical-spacing: 1px;&quot;&gt;&lt;b&gt;int main()&lt;/b&gt;&lt;/span&gt;&lt;/span&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;span style=&quot;-webkit-border-horizontal-spacing: 1px; -webkit-border-vertical-spacing: 1px;&quot;&gt;&lt;b&gt;{&lt;/b&gt;&lt;/span&gt;&lt;/span&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;span style=&quot;-webkit-border-horizontal-spacing: 1px; -webkit-border-vertical-spacing: 1px;&quot;&gt;&lt;b&gt;scanf(&quot;%d&quot;,&amp;amp;lastnumber);&lt;/b&gt;&lt;/span&gt;&lt;/span&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;span style=&quot;-webkit-border-horizontal-spacing: 1px; -webkit-border-vertical-spacing: 1px;&quot;&gt;&lt;/span&gt;&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;span style=&quot;-webkit-border-horizontal-spacing: 1px; -webkit-border-vertical-spacing: 1px;&quot;&gt;&lt;div&gt;&lt;b&gt;long n=20;&lt;/b&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;b&gt;&amp;nbsp;for(i=2;i &amp;lt; 20; i++)&lt;lastnumber;i++)&gt;&lt;/lastnumber;i++)&gt;&lt;/b&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;b&gt;&amp;nbsp;{&lt;/b&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;b&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;n=(n*i)/gcd(n,i);&lt;/b&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;b&gt;&amp;nbsp;}&lt;/b&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;b&gt;&amp;nbsp;printf(&quot; %ld \n&quot;, n);&lt;/b&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;b&gt;return 0;&lt;/b&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;b&gt;}&lt;/b&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;The euclid&#39;s algo can be implemented as:&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;div&gt;&lt;b&gt;int gcd(int a,int b)&lt;/b&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;b&gt;{&lt;/b&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;b&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp;if(a == 0)&lt;/b&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;b&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; return b;&lt;/b&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;b&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp;while(b != 0)&lt;/b&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;b&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;if (a &amp;gt; b)&lt;/b&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;b&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; a = a - b;&lt;/b&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;b&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;else&lt;/b&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;b&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; b = b - a;&lt;/b&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;b&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp;return a;&lt;/b&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;b&gt;}&lt;/b&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;b&gt;&lt;br /&gt;
&lt;/b&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;Thats all it is to the problem :D&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;br /&gt;
&lt;/div&gt;&lt;div&gt;&lt;span style=&quot;-webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; font-family: &#39;Trebuchet MS&#39;, Trebuchet, Verdana, sans-serif; line-height: 20px;&quot;&gt;&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;Please post your comments and doubts...&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;Suggestion for better algorithms are always welcome.....&lt;/span&gt;&lt;/span&gt;&lt;br /&gt;
&lt;/div&gt;&lt;/div&gt;&lt;/span&gt;&lt;/span&gt;&lt;br /&gt;
&lt;/div&gt;</content><link rel='replies' type='application/atom+xml' href='http://my-approach-to-euler.blogspot.com/feeds/5461000710535729537/comments/default' title='Post Comments'/><link rel='replies' type='text/html' href='http://my-approach-to-euler.blogspot.com/2010/01/problem-5least-evenly-divisible-number.html#comment-form' title='0 Comments'/><link rel='edit' type='application/atom+xml' href='http://www.blogger.com/feeds/5227790233130724908/posts/default/5461000710535729537'/><link rel='self' type='application/atom+xml' href='http://www.blogger.com/feeds/5227790233130724908/posts/default/5461000710535729537'/><link rel='alternate' type='text/html' href='http://my-approach-to-euler.blogspot.com/2010/01/problem-5least-evenly-divisible-number.html' title='Problem 5:Least evenly divisible number'/><author><name>Sabyasachi</name><uri>http://www.blogger.com/profile/01688296359470230325</uri><email>noreply@blogger.com</email><gd:image rel='http://schemas.google.com/g/2005#thumbnail' width='20' height='32' src='//blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgliPLdO3_DKKE4zePQbusFsYqmNhfoRzMKD9VilD375A5mc281P0nguOqrpj4qoJFvQm1dKlU4bXcaMwem0ZsySRNcTkVdroq5W4_Qqp3jTYIaK4skT0Ma68q_1CTL9g/s220/kgenesis.JPG'/></author><thr:total>0</thr:total></entry><entry><id>tag:blogger.com,1999:blog-5227790233130724908.post-564799693790110667</id><published>2009-12-29T01:53:00.000-08:00</published><updated>2009-12-29T01:53:31.196-08:00</updated><title type='text'>Problem 4: Largest palindrome number</title><content type='html'>Q.&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif; font-size: 16px;&quot;&gt;Find the largest palindrome number made from the product of two 3-digit numbers.&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;Sol.&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;The problem can be solved easily by brute force i.e. checking all the products of 3-digit numbers to be palindrome and then determining the largest among them.&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;The code for palindrome checking is easy, we can simply reverse the number and check the equality.&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;int ispalindrome(int n)&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;{&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;int temp=n,rem,sum;&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;while(n&amp;gt;0)&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;{&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;rem=n%10;&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;n=n/10;&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;sum=sum*10 + rem;&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; }&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; if(sum==temp)&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;return 1;&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; else&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;return 0;&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;}&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;&lt;br /&gt;
&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;int main()&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;{&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp;int big=0;&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp;for(i=999;i&amp;gt;=100;i--)&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;for(i=999;i&amp;gt;=100;i--)&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;if(ispalindrome(i*j)&amp;amp;&amp;amp;(big&amp;lt;(i*j)))&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; big=(i*j);&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;}&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;As you may have noticed, it takes too much time. So, I used some of my observations regarding the problem to reduce the time.&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;&lt;br /&gt;
&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;1. A palindrome number with even number of digits is always divisible by 11. So,&amp;nbsp;at least&amp;nbsp;&amp;nbsp;one of the numbers must be divisible by 11.Thus the inner loop can be decreased to be decremented by 11 each time.&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;2.There are many redundant multiplications like 999*998 and then 998*999.That must be reduced.For that we can find the nearest number to &#39;i&#39; which is divisible by 11 and is less than &#39;i&#39;.&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;It can be done easily as the number would be : i-(i%11)&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;3. The last digit of the palindrome number can&#39;t be zero as the first isn&#39;t. So, all the numbers which are multiple of 10 can be eliminated from the consideration.&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;The improved code can be:&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;int main()&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;{&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; int big=0,i,j;&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; for(i=999;i&amp;gt;=101;i--)&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; {&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; if(i%10==0)&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;continue;&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; x=i-(i%11);&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; for(j=x;j&amp;gt;=121;j-=11)&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; {&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;n=i*j;&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;if(ispalindrome(n)&amp;amp;&amp;amp; big &amp;lt; n)&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; big=n;&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; }&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;}&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;printf(&quot;%d&quot;,big);&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;}&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;Please post your comments and doubts...&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;Suggestion for better algorithms are always welcome.....&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;color: #cccccc; font-family: &#39;Trebuchet MS&#39;, sans-serif; font-size: small;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: 13px; line-height: 20px;&quot;&gt;&lt;span style=&quot;color: black;&quot;&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-size: medium; line-height: normal;&quot;&gt;This is me signing off for today....&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;</content><link rel='replies' type='application/atom+xml' href='http://my-approach-to-euler.blogspot.com/feeds/564799693790110667/comments/default' title='Post Comments'/><link rel='replies' type='text/html' href='http://my-approach-to-euler.blogspot.com/2009/12/problem-4-largest-palindrome-number.html#comment-form' title='0 Comments'/><link rel='edit' type='application/atom+xml' href='http://www.blogger.com/feeds/5227790233130724908/posts/default/564799693790110667'/><link rel='self' type='application/atom+xml' href='http://www.blogger.com/feeds/5227790233130724908/posts/default/564799693790110667'/><link rel='alternate' type='text/html' href='http://my-approach-to-euler.blogspot.com/2009/12/problem-4-largest-palindrome-number.html' title='Problem 4: Largest palindrome number'/><author><name>Sabyasachi</name><uri>http://www.blogger.com/profile/01688296359470230325</uri><email>noreply@blogger.com</email><gd:image rel='http://schemas.google.com/g/2005#thumbnail' width='20' height='32' src='//blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgliPLdO3_DKKE4zePQbusFsYqmNhfoRzMKD9VilD375A5mc281P0nguOqrpj4qoJFvQm1dKlU4bXcaMwem0ZsySRNcTkVdroq5W4_Qqp3jTYIaK4skT0Ma68q_1CTL9g/s220/kgenesis.JPG'/></author><thr:total>0</thr:total></entry><entry><id>tag:blogger.com,1999:blog-5227790233130724908.post-2163570658569180860</id><published>2009-12-07T02:29:00.000-08:00</published><updated>2010-01-24T07:49:08.617-08:00</updated><title type='text'>Problem 3: Largest Prime Factor</title><content type='html'>Q.&amp;nbsp;&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif; font-size: 16px;&quot;&gt;What is the largest prime factor of the number 600851475143 ?&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;Sol:&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;It can be seen that the largest prime factor of a number is equal to larger of its largest prime factor of its largest factor and the smallest factor.&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;i.e. largest prime factor(n)=max(smallest factor(n), largest prime factor(largest factor(n)))&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;or,largest prime factor(n)=max(smallest factor(n), largest prime factor(n/smallestfactor(n)))&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;using the relation, either the recursive or the iterative approach can be applied to solve the problem..&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;Now, it can also be seen that while finding the smallest factor, we only need to divide the number concerned by only one even number &#39;2&#39; and rest can be odd numbers. So, all the other even numbers can be eliminated from the process, thus optimizing our program.&amp;nbsp;&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;Since, a factor &#39;i&#39; can divide &#39;n&#39; multiple times, we can also put a subroutine to divide n by i multiple times until the new number comes out to be not divisible by i, further optimizing the problem...&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;Now the last and the easiest part , Coding :&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;long long int solution(long long n)&lt;br /&gt;
{&lt;br /&gt;
&lt;br /&gt;
&amp;nbsp;&amp;nbsp; &amp;nbsp; int i=2;&lt;br /&gt;
&amp;nbsp;&amp;nbsp; &amp;nbsp; long long x;&lt;br /&gt;
&amp;nbsp;&amp;nbsp; &amp;nbsp; if(n%2==0)&lt;br /&gt;
&amp;nbsp;&amp;nbsp; &amp;nbsp; {&lt;br /&gt;
&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; x=n/i;&lt;br /&gt;
&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; while(x%i==0)&lt;br /&gt;
&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;x=x/i;&lt;br /&gt;
&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; x=solution(x);&lt;br /&gt;
&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; return((i&amp;gt;x)?i:x);&lt;br /&gt;
&amp;nbsp;&amp;nbsp; &amp;nbsp; }&lt;br /&gt;
&amp;nbsp;&amp;nbsp; &amp;nbsp; else&lt;br /&gt;
&amp;nbsp;&amp;nbsp; &amp;nbsp; {&lt;br /&gt;
&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; i=3; &amp;nbsp; &amp;nbsp; &lt;br /&gt;
&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; while(i &amp;lt; sqrt ( ( double ) n ) )&lt;sqrt((double)n))&gt;&lt;sqrt((double)n))&gt;&lt;/sqrt((double)n))&gt;&lt;br /&gt;
&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; {&lt;br /&gt;
&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; if(n%i==0)&lt;br /&gt;
&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; {&lt;br /&gt;
&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; x=n/i;&lt;br /&gt;
&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; while(x%i==0)&lt;br /&gt;
&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;x=x/i;&lt;br /&gt;
&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; x=solution(x);&lt;br /&gt;
&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; return((i&amp;gt;x)?i:x);&lt;br /&gt;
&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; }&lt;br /&gt;
&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; i=i+2;&lt;br /&gt;
&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; }&lt;br /&gt;
&amp;nbsp;&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; return n;&lt;br /&gt;
&amp;nbsp;&amp;nbsp; &amp;nbsp; }&lt;br /&gt;
}&lt;br /&gt;
&lt;/sqrt((double)n))&gt;&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;As explained above, the code applies recursive approach to solve the problem and returns the largest prime factor for &#39;n&#39;..&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;br /&gt;
&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;span style=&quot;font-family: &#39;Times New Roman&#39;;&quot;&gt;&lt;/span&gt;&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;/span&gt;&lt;br /&gt;
&lt;span style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif;&quot;&gt;&lt;div style=&quot;margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;&quot;&gt;Please post your comments and doubts...&lt;br /&gt;
&lt;/div&gt;&lt;div style=&quot;margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;&quot;&gt;Better algorithms are always welcome..&lt;br /&gt;
&lt;/div&gt;&lt;/span&gt;</content><link rel='replies' type='application/atom+xml' href='http://my-approach-to-euler.blogspot.com/feeds/2163570658569180860/comments/default' title='Post Comments'/><link rel='replies' type='text/html' href='http://my-approach-to-euler.blogspot.com/2009/12/problem-3-largest-prime-factor.html#comment-form' title='0 Comments'/><link rel='edit' type='application/atom+xml' href='http://www.blogger.com/feeds/5227790233130724908/posts/default/2163570658569180860'/><link rel='self' type='application/atom+xml' href='http://www.blogger.com/feeds/5227790233130724908/posts/default/2163570658569180860'/><link rel='alternate' type='text/html' href='http://my-approach-to-euler.blogspot.com/2009/12/problem-3-largest-prime-factor.html' title='Problem 3: Largest Prime Factor'/><author><name>Sabyasachi</name><uri>http://www.blogger.com/profile/01688296359470230325</uri><email>noreply@blogger.com</email><gd:image rel='http://schemas.google.com/g/2005#thumbnail' width='20' height='32' src='//blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgliPLdO3_DKKE4zePQbusFsYqmNhfoRzMKD9VilD375A5mc281P0nguOqrpj4qoJFvQm1dKlU4bXcaMwem0ZsySRNcTkVdroq5W4_Qqp3jTYIaK4skT0Ma68q_1CTL9g/s220/kgenesis.JPG'/></author><thr:total>0</thr:total></entry><entry><id>tag:blogger.com,1999:blog-5227790233130724908.post-4265094560026404462</id><published>2009-12-02T07:38:00.000-08:00</published><updated>2009-12-07T14:04:35.498-08:00</updated><title type='text'>Problem 2: Sum of even fibonacci numbers</title><content type='html'>Q.Find the sum of all the even-valued terms in the sequence which do not exceed four million.&lt;br /&gt;
&lt;br /&gt;
&lt;br /&gt;
Sol: &lt;br /&gt;
This problem too is a trivial one if the brute force approach is followed. But on observing the fibonacci series, it is observed that there is an even number every three steps....&lt;br /&gt;
1 1 2 3 5 8 13 21 34 55 89 144 .......&lt;br /&gt;
So, instead of checking for divisibility by 2 each time an element is calculated, every third fibonacci number can be added upto 4 million to find the result.&lt;br /&gt;
&lt;br /&gt;
The code to solve the problem can then be :&lt;br /&gt;
&lt;br /&gt;
&amp;nbsp;&amp;nbsp; i=1,j=2,d=0,x=0; &lt;br /&gt;
&amp;nbsp;&amp;nbsp; long s=0; &lt;br /&gt;
&amp;nbsp;&amp;nbsp; while(j&amp;lt;4000000) &lt;br /&gt;
&amp;nbsp;&amp;nbsp; { &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; s=s+j; &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; while(d&amp;lt;=2) &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; { &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; x=i+j; &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; i=j; &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; j=x; &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; d++; &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; } &lt;br /&gt;
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; d=0;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp; &lt;br /&gt;
&amp;nbsp;&amp;nbsp; } &lt;br /&gt;
&amp;nbsp;&amp;nbsp; cout &amp;lt;&amp;lt; s&lt;s&gt;&lt;/s&gt;&lt;br /&gt;
&lt;s style=&quot;text-decoration: none;&quot;&gt;}&lt;br /&gt;
&lt;br /&gt;
As explained, the code calculates three elements in each loop and adds the third number to the sum.&lt;br /&gt;
&lt;br /&gt;
Please post your comments...&lt;br /&gt;
Better algorithms are always welcome..&lt;br style=&quot;text-decoration: line-through;&quot; /&gt;&lt;span class=&quot;Apple-style-span&quot; style=&quot;text-decoration: line-through;&quot;&gt; &lt;/span&gt;&lt;/s&gt;</content><link rel='replies' type='application/atom+xml' href='http://my-approach-to-euler.blogspot.com/feeds/4265094560026404462/comments/default' title='Post Comments'/><link rel='replies' type='text/html' href='http://my-approach-to-euler.blogspot.com/2009/12/problem-2-sum-of-even-fibonacci-numbers.html#comment-form' title='0 Comments'/><link rel='edit' type='application/atom+xml' href='http://www.blogger.com/feeds/5227790233130724908/posts/default/4265094560026404462'/><link rel='self' type='application/atom+xml' href='http://www.blogger.com/feeds/5227790233130724908/posts/default/4265094560026404462'/><link rel='alternate' type='text/html' href='http://my-approach-to-euler.blogspot.com/2009/12/problem-2-sum-of-even-fibonacci-numbers.html' title='Problem 2: Sum of even fibonacci numbers'/><author><name>Sabyasachi</name><uri>http://www.blogger.com/profile/01688296359470230325</uri><email>noreply@blogger.com</email><gd:image rel='http://schemas.google.com/g/2005#thumbnail' width='20' height='32' src='//blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgliPLdO3_DKKE4zePQbusFsYqmNhfoRzMKD9VilD375A5mc281P0nguOqrpj4qoJFvQm1dKlU4bXcaMwem0ZsySRNcTkVdroq5W4_Qqp3jTYIaK4skT0Ma68q_1CTL9g/s220/kgenesis.JPG'/></author><thr:total>0</thr:total></entry><entry><id>tag:blogger.com,1999:blog-5227790233130724908.post-4811097133011525290</id><published>2009-12-01T15:42:00.000-08:00</published><updated>2009-12-01T16:19:42.723-08:00</updated><title type='text'>Problem 1 : Sum of numbers</title><content type='html'>&lt;span class=&quot;Apple-style-span&quot; style=&quot;font-family: &#39;Trebuchet MS&#39;, sans-serif; font-size: 16px;&quot;&gt;Q. Find the sum of all the multiples of 3 or 5 below 1000.&lt;/span&gt;&lt;br /&gt;
&lt;br /&gt;
Sol:&lt;br /&gt;
This one must be the easiest problem on Euler.. It can be solved easily without programming. &lt;br /&gt;
For an arithmetic progression whose first term is &#39;a&#39;, last term is &#39;l&#39; and no. of elements is n, the sum is given by&lt;br /&gt;
n/2 * (a+d).&lt;br /&gt;
So, since we are required to calculate the sum of numbers up to 1000 divisible by either 3 or 5, we just calculate the sum of numbers divisible by 3(S1) and add it to sum of numbers divisible by 5(S2).Now taking care that those divisible by both 3 and 5(i.e. those divisible by 15) have been summed up twice,we subtract the sum of numbers divisible by 15(S3) from it. Nice and easy!!!!&lt;br /&gt;
&lt;br /&gt;
No. of numbers divisible by 3=999/3=333&lt;br /&gt;
S1= 333/2 * (3+999)=166833&lt;br /&gt;
No. of numbers divisible by 5=995/5=199&lt;br /&gt;
S2=199/2 * (5+995)=99500&lt;br /&gt;
NO. of numbers divisible by 15= 990/15=66&lt;br /&gt;
S3=66/2 * (15+990)=33165&lt;br /&gt;
&lt;br /&gt;
Result= S1 + S2 -S3= 233168&lt;br /&gt;
&lt;br /&gt;
Please post your comments...&lt;br /&gt;
Better algorithms are always welcome..</content><link rel='replies' type='application/atom+xml' href='http://my-approach-to-euler.blogspot.com/feeds/4811097133011525290/comments/default' title='Post Comments'/><link rel='replies' type='text/html' href='http://my-approach-to-euler.blogspot.com/2009/12/problem-1.html#comment-form' title='0 Comments'/><link rel='edit' type='application/atom+xml' href='http://www.blogger.com/feeds/5227790233130724908/posts/default/4811097133011525290'/><link rel='self' type='application/atom+xml' href='http://www.blogger.com/feeds/5227790233130724908/posts/default/4811097133011525290'/><link rel='alternate' type='text/html' href='http://my-approach-to-euler.blogspot.com/2009/12/problem-1.html' title='Problem 1 : Sum of numbers'/><author><name>Sabyasachi</name><uri>http://www.blogger.com/profile/01688296359470230325</uri><email>noreply@blogger.com</email><gd:image rel='http://schemas.google.com/g/2005#thumbnail' width='20' height='32' src='//blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgliPLdO3_DKKE4zePQbusFsYqmNhfoRzMKD9VilD375A5mc281P0nguOqrpj4qoJFvQm1dKlU4bXcaMwem0ZsySRNcTkVdroq5W4_Qqp3jTYIaK4skT0Ma68q_1CTL9g/s220/kgenesis.JPG'/></author><thr:total>0</thr:total></entry><entry><id>tag:blogger.com,1999:blog-5227790233130724908.post-8394518281611059178</id><published>2009-11-30T09:46:00.000-08:00</published><updated>2009-12-07T14:17:22.200-08:00</updated><title type='text'>I start euler........</title><content type='html'>Today, I finally started solving problems on project euler.I am really a very lazy person, so when I started it, I thought there must be some way of keeping me doing it. Maybe writing a blog on it will help,because if there are no more questions to solve, then how will I continue my blog....&lt;br /&gt;
So, here it is..&lt;br /&gt;
My adventure on Project Euler....</content><link rel='replies' type='application/atom+xml' href='http://my-approach-to-euler.blogspot.com/feeds/8394518281611059178/comments/default' title='Post Comments'/><link rel='replies' type='text/html' href='http://my-approach-to-euler.blogspot.com/2009/11/i-start-euler.html#comment-form' title='0 Comments'/><link rel='edit' type='application/atom+xml' href='http://www.blogger.com/feeds/5227790233130724908/posts/default/8394518281611059178'/><link rel='self' type='application/atom+xml' href='http://www.blogger.com/feeds/5227790233130724908/posts/default/8394518281611059178'/><link rel='alternate' type='text/html' href='http://my-approach-to-euler.blogspot.com/2009/11/i-start-euler.html' title='I start euler........'/><author><name>Sabyasachi</name><uri>http://www.blogger.com/profile/01688296359470230325</uri><email>noreply@blogger.com</email><gd:image rel='http://schemas.google.com/g/2005#thumbnail' width='20' height='32' src='//blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgliPLdO3_DKKE4zePQbusFsYqmNhfoRzMKD9VilD375A5mc281P0nguOqrpj4qoJFvQm1dKlU4bXcaMwem0ZsySRNcTkVdroq5W4_Qqp3jTYIaK4skT0Ma68q_1CTL9g/s220/kgenesis.JPG'/></author><thr:total>0</thr:total></entry></feed>