So, this problem asked us to find the first triangular number that has over 500 divisors.
When I was solving this, I totally forgot about the triangular part so I tried to find the first instance of number that had over 500 divisors. (It was 14414400)
When I ran that code, it took almost 2 minutes to arrive at an answer! Other than that, the answer was wrong too! (duh..)
After carefully reading the problem again, I fixed "n++" to "n += i++" to only check for triangular numbers.
The problem was solved using Trial Division method.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main()
{
long int n = 0;
long int i = 1;
while (findNumberOfDivisors(n) < 500){
n += i++; //Used n++ when I understood the problem wrong.
}
printf("%ld\n", n);
return 0;
}
int findNumberOfDivisors(long n){
int number = 2;
int squareRoot = (int) sqrt(n);
long int i;
for (i = 2; i <= squareRoot; i++){
if (n % i == 0){
number += 2;
}
}
if (squareRoot * squareRoot == n)
number--;
return number;
}
This problem was very similar to problem 8 of Project Euler.
I used the same concept proposed in optimizing the code (click this)
Optimizations Skipping product upon seeing certain "low" digit values.
Upon inspection of product of randomly chosen 4 numbers, which in my case was (78*78*96*83) resulting in a product of 48477312, we can arrive at a conclusion of ignoring any product containing numbers less than or equal to 49.
This is because the highest possible product with only 3 digits is 99 * 99 * 99 = 970299. So, simply dividing 48477312/970299 = 49.96... So, even in the best case scenario with the number 49, we cannot exceed the arbitrarily found product. Therefore, we don't even need to compute for products with number less than or equal to 49.
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;
}
