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;
}
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;
}
Very simple program that uses factorization.
No need to create sieve of Eratosthenes like I did in the following post. [Project Euler] Problem 3a
In my version, I originally used unsigned long long int but I saw from the answer forum that we can use __int64.
Anyways, I knew from the number that it's not divisible by 2 so I started from 3 and then only checked for odd divisors so that I can halve the execution time.
The best time was 0.007s but averaged around 0.011s.
#include
int main()
{
__int64 number = 600851475143, divisor = 3;
while (number > 1) {
if (!(number % divisor)) {
number /= divisor;
divisor -= 2;
}
divisor += 2;
}
printf("%d\n", divisor);
return 0;
}
This one is as easy as previous problems.
However, since it has been a long time since I have coded in C or in fact, any languages, I wanted to solve this problem incorporating some file handling, and linked list.
It is a weird choice and probably the most inefficient way of solving this.
The result I have gotten was incorrect because of how integer artithmetics in __int64 types.
The correct answer can be found from here: [Project Euler] Problem 3
How Sieve of Eratosthenes is Created
File Handling
I implemented sieve of Eratosthenes (for more details, click the link)in C and have saved them into a file.
The number I am working with is a not a huge number 600851475143, so using sieve of Eratosthenes is probably one of the slowest methods available.
However, for practice, I have used this method.
In the file, only the prime numbers and the last number the code has executed before were stored.
This was to eliminate computing power required to reprocess some numbers which have been determined to be prime or not.
So, if the computer has created sieve of Eratosthenes before up to the number 15.
The file would appear like:
2 3 5 7 11 13 15
Each number would be separated by a space (' ') with the last number representing the number it has calculated up until.
Linked List Speed
Unlike the algorithm presented in the gif image in the Wikipedia page of sieve of Eratosthenes, I have decided to delete values which have already been determined to be a multiple of a prime number. In other words, if there was 100,000 values to work with, instead of checking nearly 100,000 values for each prime number found, the number of values checked would decrease.
Memory
In terms of memory cost during execution time, using linked list would be less than array as well. Since an array uses the memory for the entire duration of execution. However, this statement would only be true if there are
However, for such a small number, this would not matter as much. However, for something like 50 digit number, it will matter.
The primary reason for using linked list is again, for my practice.
Optimizations
I. We only need to check prime values up to square root of a number to find the largest prime factor of number
I believe this statement is wrong but I have implemented this into my code. I obscurely remembered the statement and sadly, I remembered incorrectly. So, after writing the entire code, I have tried to confirm it on the internet but I was wrong! However, this was not the reason why I was left with an incorrect answer.
II. We only need to check for multiples of values up to half of the maximum value in sieve of Eratosthenes
The above statement is true. Sieve of Eratosthenes uses the concept of multiples of a prime number to eliminate any non-prime numbers since any numbers can be factored into only the prime numbers. So, when processing sieve of Eratosthenes, I have checked for multiples only until values less than (maxVal / 2 + 1).
As shown in while (linkList -> curr != NULL && linkList->curr->value < num / 2 + 1)
III. We can eliminate even numbers to check except for 2
For obvious reasons, 2 (prime number) is not eliminated from sieve of Eratosthenes. Then we know multiples of 2 are even numbers, so we can immediately even numbers in our sieve of Eratosthenes to halve the execution time.
As shown in +=2 in code
Code
I had three files: main.c
#include "linkedList.h"
#define NUM_LENGTH 15
__int64 initSofE(FILE *fp, int status, __int64 number, LL *linkList1);
__int64 getNextOddNumber(__int64 n);
int insertNode(LL *linkList1, __int64 val);
int deleteNode(LL *linkList1);
void printNumberOfNodes(LL *linkList1);
int processSofE(LL *linkList, __int64 num);
__int64 getGreatestPrimeFactor(LL *linkList, __int64 number);
int main(){
__int64 origNumber = 600851475143LL;
__int64 number = (long long int)sqrt(600851475143LL);
__int64 lastNumberProcessedBefore = 0;
int status = 0; /* 0 = file does not exist, need to initialize the entire LL
1 = file exists, need to initialized with the numbers
inside the file
*/
char filename[] = "C:\\Users\\parkk\\Project Euler\\Problem0003a\\SofE.txt";
FILE *ifp, *ofp;
ifp = fopen (filename, "r");
LL linkList1;
linkList1.head = NULL;
// File does not exist
if (ifp == NULL){
fprintf(stderr, "Can't open input file!\n");
fclose(ifp);
status = 0;
} else {
status = 1;
fclose(ifp);
}
ofp = fopen (filename, "w+");
if (ofp != NULL){
lastNumberProcessedBefore = initSofE(ofp, status, number, &linkList1);
if (!lastNumberProcessedBefore){
fprintf(stderr, "Error in filling linked list!\n");
return -1;
}
} else {
fprintf(stderr, "Error in opening file in a+ mode\n");
// No returning -1 since it just means the file does not exist
}
// Now that sieve has been initialized, the sieve must be processed
printNumberOfNodes(&linkList1);
if (!processSofE(&linkList1, number)){
fprintf(stderr, "Error in processing S of E\n");
return -1;
}
printToFile(&linkList1, ofp, number, lastNumberProcessedBefore);
printNumberOfNodes(&linkList1);
printf("%d\n", getGreatestPrimeFactor(&linkList1, origNumber));
fclose(ofp);
return 0;
}
void printToFile(LL *linkList, FILE *fp, __int64 number, __int64 lastNumber){
int status = 0;
linkList->curr = linkList->head;
while (linkList -> curr != NULL){
if (linkList->curr->value > lastNumber){
fprintf(fp, " %d", linkList->curr->value);
status = 1;
}
linkList->curr = linkList->curr->next;
}
if (status)
fprintf(fp, "%d\n", number);
}
__int64 getGreatestPrimeFactor(LL *linkList, __int64 number){
__int64 greatestPrimeFactor = 0;
Node *p;
p = linkList->head;
if (p == NULL){
fprintf(stderr, "S of E is empty.");
return -1;
}
while (p != NULL){
if (number % p->value == 0){
greatestPrimeFactor = p->value;
}
p = p->next;
}
printNumberOfNodes(linkList);
return greatestPrimeFactor;
}
int processSofE(LL *linkList, __int64 num){
__int64 div = 0, counter = 0;
Node *a;
if (linkList -> head == NULL){
fprintf(stderr, "No node in linkList [processSofE()]\n");
return 0;
}
if (linkList->head->next == NULL){
fprintf(stderr, "Only one node in linkList [processSofE()]\n");
return 0;
}
a = linkList->head->next;
if (a->next == NULL){
fprintf(stderr, "Only two nodes in linkList [processSofE()]\n");
return 0;
}
linkList->prev = a;
linkList->curr= a->next;
while (a->next != NULL){
div = a -> value;
linkList -> prev = a;
linkList -> curr = a -> next;
while (linkList -> curr != NULL && linkList->curr->value < num / 2 + 1){
if (linkList->curr->value % div == 0){
linkList->prev->next = linkList->curr->next;
free(linkList->curr);
linkList->curr = linkList->prev->next;
}
if (linkList -> curr != NULL){
linkList->prev = linkList->curr;
linkList->curr = linkList->curr->next;
}
}
a = a -> next;
}
return 1;
}
__int64 initSofE(FILE *fp, int status, __int64 number, LL *linkList1){
Node *newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL){
fprintf(stderr, "Error in allocating for the first node");
return 0;
}
newNode -> value = 2;
newNode -> next = linkList1->head;
linkList1->head = newNode;
linkList1->curr = newNode, linkList1->prev = newNode;
__int64 i;
char c, *s;
__int64 prime_num;
// File does not exist
if (status == 0){
// Create a linked list of possible prime number candidates
for (i = 3; i <= number; i+=2){
insertNode(linkList1, i);
if (linkList1->curr == NULL){
fprintf(stderr, "Error in insertNode()\n");
return 0;
}
}
// File exists
} else if (status == 1){
s = (char*)malloc(sizeof(char) * NUM_LENGTH);
if (s == NULL){
fprintf(stderr, "Error in allocating memory for file reading (*s)");
return 0;
}
// Initialize the string
for (i = 0; i < NUM_LENGTH; i++){
s[i] = '\0';
}
i = 0;
//Read the file
do{
c = fgetc(fp);
if (c == ' ' || c == EOF){
prime_num = strtoull(s, &s, 10); // Convert string to long long int
i = 0;
if (prime_num < number){
if (!insertNode(linkList1, prime_num))
return 0;
}
}else{
s[i++] = c;
}
}while (c != EOF);
deleteNode(linkList1); // The last number shows until what number has been checked for prime numbers
if (number > prime_num){
__int64 a = getNextOddNumber(prime_num);
while (a <= number){
if (!insertNode(linkList1, a)){
return 0;
}
a+=2;
}
}
free(s);
}
return 1;
}
__int64 getNextOddNumber(__int64 n){
if (n % 2 == 0){
return n+ 1;
} return n;
}
void printNumberOfNodes(LL *linkList1){
__int64 counter = 0;
Node *c = linkList1->head;
while (c != NULL){
//printf("%llu\n", c -> value);
counter++;
c = c -> next;
}
printf("counter: %d\n", counter);
}
linkedList.c
#include "linkedList.h"
// Adds newNode with value val to the node after which curr is pointing to
// Precondition: the linked list will always contain at least one node
int insertNode(LL *linkList1, __int64 val){
Node *newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL){
printf("Unable to allocate memory to newNode in insertNode()");
return 0;
}
if (linkList1 -> curr == NULL){
linkList1 -> curr = linkList1 -> head;
while (linkList1->curr->next != NULL)
linkList1->curr = linkList1->curr->next;
}
newNode -> value = val;
newNode -> next = linkList1 -> curr -> next;
linkList1 -> curr -> next = newNode;
linkList1 -> prev = linkList1->curr;
linkList1 -> curr = newNode;
return 1;
}
// Deletes a node where curr is pointing to
// Precondition: first node is not deleted
// curr is always pointing at a node in the linked list
int deleteNode(LL *linkList1){
if (linkList1 -> head == NULL)
return 0;
linkList1->prev->next = linkList1->curr->next;
free(linkList1->curr);
linkList1->curr=linkList1->prev->next;
return 1;
}
Despite all the loopholes, the reason behind the incorrect answer was surprisingly due to integer arithmetics of __int64 types. The answer the code spat out was 486847 which is much larger than the correct answer.
This was because 600851475143 % 486847 = 0 instead of 20.
This miscalculation has caused 486847 to be the largest prime factor of 600851475143.
The moment I found out the problem, I dropped everything because I felt I had enough practice on link lists and file handling and it was time to move on.
Loop Holes
the number to create sieve of Eratosthenes up until must be greater than 2 or it will fail the next time it executes while file exists
the code has segmentation faults when the file exists but is empty
after successfully outputting sieve of Eratosthenes to file, when the program is run again, it correctly retrieves the data but outputs the results incorrectly (This has been fixed by opening the file with "w+" mode despite the fact that the file needs to be rewritten from the start, slowing the execution time as a result.)
No need to store lots of things for just addition
I remember when I first started, I put the Fibonacci series in an array and then traversed through them to add them all up.
Ahhhh good times.
#include <stdio.h>
#include <stdlib.h>
int main()
{
int a = 1, b = 2;
int c, total = 2;
while (c <= 4000000){
c = a + b;
a = b;
b = c;
if (!(c % 2))
total += c;
}
printf("%d\n", total);
}
#include <stdio.h>
#include <stdlib.h>
int main()
{
int total = 0, i;
for (i = 1; i < 1000; i++){
if (!(i % 5))
total += i;
else if (!(i % 3))
total += i;
}
printf("%d\n", total);
return 0;
}
