There's not much to explain here, just summing all the primes below 2,000,000.
I believe the technique used for problem 7 (sieve of erastosthenes) is the same as the technique used in this problem with some minor tweaks.
I should probably create a sieve of erastosthenes since the questions from Project Euler deal with a lot of primes..
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
int sieve[2000000];
int main(){
memset(sieve, -1, sizeof(int)*2000000);
sieve[2] = 1;
int i, j, div;
for (i = 4; i <= 2000000; i+=2){
sieve[i] = 0;
}
i = 3, j = 3, div = 3;
while (i <= 2000000){
if (sieve[i] == -1){
div = i;
sieve[i] = 1;
for (j = div*2; j<=2000000; j+=div)
sieve[j] = 0;
}
i++;
}
__int64 sum = 0;
i = 2;
while(i < 2000000){
if (sieve[i] == 1)
sum += i;
i++;
}
printf("%lld\n", sum);
return 0;
}
Algorithm
I decided to approach this problem at more mathematical angle because without doing so, the program will need to iterate through 2 variables instead of 1 variable to arrive at an answer, drastically reducing the runtime.
Optimization
A relationship between two variables has been found on paper through algebra, so, O(n) was achieved instead of O(n^2).
a + b + c = 1000 ... (1)
a^2 + b^2 = c^2 ... (2)
Solving a^2 + b^2 = (1000-a-b)^2,
a = 1000 + 500,000 / (b - 1000) ... (3)
Iterate through b to solve for a. If a is a natural number, then we have arrived at our solution.
#include <stdio.h>
#include <stdlib.h>
int main()
{
int b = 1, c = 1;
float a=0;
for (b = 1; b < 998; b++ ){
a = 1000.0 + 500000.0/(b-1000.0);
if ( a == (long)a) // Check for integer max and min for general use to check if integer
break;
}
c = 1000 - a - b;
printf("%f\n", a*b*c);
return 0;
}
Algorithm
This is the brute force way of solving the problem in C.
It is fairly straight forward. Since the question asks us to find the greatest product in five consecutive digits, one loop (w/ iterator i) looped through the entire number, while another loop (w/ iterator j) inside the loop worked with next 4 digits to find the product.
In short, the code just slides 5-digit width along the number to read and find the product.
Possible Optimizations
Since the number is only 1000 digits, I have not made any at optimization in the code posted below. Maybe later, I can revisit it. But here are number of ways of optimizing the code:
1) Using the product from before to calculate the current "slide" of digits.
Just take a look at first 10 digits of the number given "7316717653"
7 * 3 * 1 * 6 * 7 = prod1
3 * 1 * 6 * 7 * 1 = prod2
1 * 6 * 7 * 1 * 7 = prod3
6 * 7 * 1 * 7 * 6 = prod4
7 * 1 * 7 * 6 * 5 = prod5
1 * 7 * 6 * 5 * 3 = prod6
From the example, we can see a pattern that the calculation of the "slide" has their first 4 digit product coincide with last 4 digit product calculation of the previous slide.
By storing the last 4 digit product for the calculation of the next "slide," we can prevent the computer from recalculating, which reduces our runtime. (Only one loop required to implement this)
2) Skipping product upon seeing certain "low" digit values.
Upon inspection of product of randomly chosen 5 consecutive digits, which in my case was "66896" resulting in a product of 15552, we can arrive at a conclusion of omitting any "slide" containing values less than 2.
This is because the highest possible product with only 4 digits within the slide is 9*9*9*9 = 6561. So, simply dividing 15552/6561 = 2.37... So, in order to get a number higher than 15552 (which we found by inspection), we need to have a digit value higher than 2.37. In conclusion, omitting any calculation of a "slide" containing digit values less than 2 is valid.
#include <stdio.h>
#include <stdlib.h>
#define S_LENGTH 1000
int main()
{
char *s = "73167176531330624919225119674426574742355349194934"
"96983520312774506326239578318016984801869478851843"
"85861560789112949495459501737958331952853208805511"
"12540698747158523863050715693290963295227443043557"
"66896648950445244523161731856403098711121722383113"
"62229893423380308135336276614282806444486645238749"
"30358907296290491560440772390713810515859307960866"
"70172427121883998797908792274921901699720888093776"
"65727333001053367881220235421809751254540594752243"
"52584907711670556013604839586446706324415722155397"
"53697817977846174064955149290862569321978468622482"
"83972241375657056057490261407972968652414535100474"
"82166370484403199890008895243450658541227588666881"
"16427171479924442928230863465674813919123162824586"
"17866458359124566529476545682848912883142607690042"
"24219022671055626321111109370544217506941658960408"
"07198403850962455444362981230987879927244284909188"
"84580156166097919133875499200524063689912560717606"
"05886116467109405077541002256983155200055935729725"
"71636269561882670428252483600823257530420752963450";
int i, j, greatestProd = 0, prod;
for (i = 0; i < S_LENGTH-4;i++){
prod = 1;
for (j = 0; j < 5; j++){
prod *= (s[i+j]-'0');
}
if (prod > greatestProd)
greatestProd = prod;
}
printf("%d\n", greatestProd);
return 0;
}
Implemented Sieve of Eratosthenes in an array.
I refrained from using % (Modulus). I am unsure of how modulus works in C but I believed that it will hinder the performance when working with large numbers. Instead, I have used a for loop with changing steps.
One way of optimizing this would be to somehow delete the non-prime numbers from the array and don't even check the array.
However, since the state of a number is represented in respect to position number of the array, I can not think of a faster way to use the same array to solve the problem.
I have implemented a dirty linked list code in Problem 3a.
I say it's dirty because it works without declaring temporary pointers and does not fully traverse the list to delete a value.
Anyways, without further ado, here is the code I have used.
Feel free to leave a comment.
#include <stdio.h>
#include <stdlib.h>
int sieve[1000000];
int main(){
memset(sieve, -1, sizeof(int)*1000000);
sieve[2] = 1;
int i, j, div;
for (i = 4; i <= 1000000; i+=2){
sieve[i] = 0;
}
i = 3, j = 3, div = 3;
while (i <= 1000000){
if (sieve[i] == -1){
div = i;
sieve[i] = 1;
for (j = div*2; j<=1000000; j+=div)
sieve[j] = 0;
}
i++;
}
int counter = 0;
i = 2;
while (counter != 10001){
if (sieve[i++] == 1)
counter++;
}
printf("%d\n", --i);
return 0;
}
All we need to find was least common multiple for numbers 1 to 20.
We could have done it easily by hand but I wanted to develop an algorithm for this :)
Very simple program.
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
uint64_t gcd(uint64_t a, uint64_t b);
int main( )
{
uint64_t initialFactor = 2, finalFactor = 20;
uint64_t lcm = 1, i;
for (i = initialFactor; i <= finalFactor; i++){
lcm*= i / gcd(lcm, i);
}
printf("%llu\n",lcm);
return 0;
}
//Euclidean greatest common divisor algorithm
uint64_t gcd(uint64_t a, uint64_t b){
if (a == 0) return b;
return gcd(b%a, a);
}
Probably the fastest I can with isPalindrome()...
Brute Force way!
I can't think of any way of not doing this brute force.
Time to check the Project Euler forum ;)
#include <stdio.h>
#include <stdlib.h>
int main()
{
int a = 999, b = 999, prod = 0, greatestProd = 0;
while (a > 0 && b > 0){
prod = a * b;
if (prod > greatestProd && isPalindrome(prod))
greatestProd = prod;
if (b-- == 1){
b = 999;
a--;
}
}
printf("%d\n", greatestProd);
return 0;
}
int isPalindrome(int num){
int rev = 0, num_copy = num;
while (num > 0){
rev = rev * 10 + num % 10;
num /= 10;
}
return (num_copy == rev) ? 1 : 0;
}
