## Project Euler

Problem 1:  http://projecteuler.net/problem=1 : Find the sum of all the multiples of 3 or 5 below 1000.

Solution: Please download the file https://sites.google.com/site/pandre/files/SumMultiples3or5Below1000.zip then UnZip it to two files: SumMultiples3or5.C (with C Source Code) and SumMultiples3or5.EXE with Console Application (executable in CMD console Window under Windows 7 or above). Also you can see the code for Problem 1 below (after Euler’s portrait).

Problem 5: http://projecteuler.net/problem=5 : Smallest Multiple – What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Solution: Please download the ZIP file https://sites.google.com/site/pandre/files/SmallestMultipleFor1To20.zip and UnZip it to two files: SmallestMultipleFor1To20.C (with ANSI-compatible C Source Code) and SmallestMultipleFor1To20.EXE with Console Application (executable in CMD console Window under Windows 7 or above). Also you can see the code for Problem 5 below (after Euler’s portrait and below the code for Problem 1).

Problem 85: http://projecteuler.net/problem=85: Although there exists no rectangular grid that contains exactly two million rectangles, find the area of the grid with the nearest solution. Here is an example with 2 by 3 grid, containing 18 rectangles: Solution: Please download the file: https://sites.google.com/site/pandre/files/CountingRectangles.zip and UnZip it to 2 files: CountingRectangles.C (with ANSI-compatible C Source Code) and CountingRectangles.EXE with Console Application (executable in CMD console Window under Windows 7 or above). Also you can see the code for Problem 85 below (after Euler’s portrait and below the code for Problem 5). #### C Source Code for Problem 1 (All multiples of 3 or 5):

```#include<stdio.h>
int main( void )
{
// http://projecteuler.net/problem=1 ,
// Find the sum of all the multiples of 3 or 5 below 1000.
// Compiled with VC++ 2010 Express as Console Application
int Limit=999; // Upper Limit MINUS 1
int AmountM3=Limit/3, AmountM5=Limit/5, AmountM15=Limit/15;
// Amount of Multiples of 3, 5 and 15 below 1000
int LastM3=3*AmountM3, LastM5=5*AmountM5, LastM15=15*AmountM15;
// Last Multiple of 3, 5 and 15 below 1000
int Sum;
// to accumulate the Sum of Arithmetic Series/Progression:
// a*1+a*2+...+a*n = a*(1+2+...+n) = a*n*(n+1)/2,
// in our test a = 3, 5 and 15
// we calculate 3 Sums for 3 Progressions:
// Multiples of 3 PLUS Multiples of 5
// MINUS (to avoid double counting) Multiples of 15
Sum = (AmountM3*(3+LastM3)+AmountM5*(5+LastM5)-
AmountM15*(15+LastM15))/2;
printf("sum is %d\n", Sum);
// getchar(); // prevents Console to close; comment/uncomment
return 0;
}```

#### C Source Code for Problem 5 (Smallest Multiple):

```#include <stdio.h>
#include <math.h>
// http://projecteuler.net/problem=5 , Smallest Multiple
// Smallest Number>0 that is divisible by all of the Integers <=20
// Compiled with VC++ 2010 Express as Console Application
// Compiled As ANSI-compatible C Code
short IsPrime(int n); // Function to Test if Number n is Prime
// Output:
// "Smallest Multiple of the numbers from 1 to 20 is 232792560"
main()
{
int i, Limit=20, Exponent;
long LCM = 1; // Least Common Multiple or LCM
double X = Limit, LnLimit = log(X), Y; // making log and pow happy
// Algorithm:
// 1. Take all the primes in the list.
// 2. For all the primes, pi, find the largest mi where pow(pi,mi)≤n.
// 3. Multiply all these powers of primes together.
// For example, given [1,2,3,...,20], we have
// p1=2 and m1=4, p2=3 and m2=2 and all other mi=1
// therefor LCM(1,2,3,...,20)=(2**4)×(3**2)×5×7×11×13×17×19

for (i=2; i<=Limit; i++)
{
if (IsPrime(i) == 1)
{
Y = i; // conversion from int to double
Exponent = (int)(LnLimit/log(Y));
if (Exponent < 2) LCM = LCM*i;
else LCM=LCM*(long)pow(Y, Exponent);
}
}
printf("Project Euler Problem 5: Least Common Multiple\n");
printf("Smallest Multiple of the numbers from 1 to 20 is %d\n", LCM);
//getchar(); // prevents Console to close; comment/uncomment
}
short IsPrime(int n)
{
if(n==1) return 0; // 1 is not a Prime
else if(n<4) return 1; // 2 and 3 are both Primes
else if(n%2==0) return 0; // Even Numbers are not Primes
else if(n<9) return 1; // leftover below 9 are 5 and 7 as Primes
else if(n%3==0) return 0; // Mutilples of 3 are not Primes
else
{ // at least one Divisor for non-Primes is <= sqrt(n)
int r=(int)sqrt(n*1.0);
int f=5;
while(f<=r)
{ // prime greater than 3 can be written in the form 6k+/-1
if(n%f==0) return 0; // f as 6k-1
if(n%(f+2)==0) return 0; // f as 6k+1
f=f+6;
}
return 1; // n is Prime
}
}```

#### C Source Code for Problem 85 (Counting Rectangles in Grid):

```#include <stdio.h>
#include <math.h>
int main (void)
{
// http://projecteuler.net/problem=85
// Find the Grid with the nearest to 2000000 millions rectangles
int Target = 2000000, hlTarget = 4*Target;
int Rectangles, Diff, Delta = 10;
int Height, Length, GridSize; // Assume: Height (of Grid) <= Length
// Height*(Height+1)*Length*(Length+1) <= hlTarget
// therefor pow(Height,4) < hlTarget
int HLines, VLines, MinLength, MaxLength;
// HLines = Height*(Height+1)/2 ways for 2 lines horizontally
// VLines = Length*(Length+1)/2 ways for 2 lines horizontally
int MaxHeight = (int)floor(pow(hlTarget, 0.25)); // = 53
double hlfTarget = (double)hlTarget, hlTargetLess1=hlfTarget-1.;
printf("Proj.Euler P.85: Found Grid close to 2000000 Rectangles:\n");

for (Height = 1; Height < MaxHeight; Height++)
{
HLines = Height*(Height+1); // saving division on 2
MinLength = (int)floor(sqrt(hlTargetLess1/HLines));
MaxLength = (int)ceil(sqrt(hlfTarget/HLines));
// Only Grids with close to 2 Millions of Rectanges
for (Length = MinLength; Length <= MaxLength; Length++)
{
VLines = Length*(Length+1); // saving division on 2
Rectangles = HLines*VLines/4;
Diff = abs(Rectangles - Target);
if (Diff < Delta)
{
GridSize = Height*Length;
printf(
"Grid is %d, Height= %d, Length= %d, Grid contains %d Rectangles\n",
GridSize, Height, Length, Rectangles);
}
}
}
// getchar(); // prevents Console to close; comment/uncomment
return 0;
}
```