See About Project Eulerhttp://projecteuler.net/about

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:

p_085

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).

Euler

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;
}
 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s