Solved Problems

Since developing a love for programming, I have always tried to solve any problem on my own. In this pursuit, I have solved several problems, including those from Project Euler some books and from the preparation stages for the Informatics Olympiad. I have tried to include all the problems that I have solved on my own approach up to this day.

Problem 1-

If we list all the natural numbers below \(10\) that are multiples of \(3\) or \(5\), we get \(2, 5, 6\) and \(9\). The sum of these multiples is \(23\). Find the sum of all the multiples of \(3\) or \(5\) below \(1000\). (Problem Statement)

Solve-

In order to solve this problem, we are go through a little bit of mathematical intuition. Since we are called to determine the sum of all the numbers \((1, 1000)\) which are divislbe by \(3\) or \(5\), we need to list all the numbers multiple of \(3\) or \(5\). So, we need to run a loop under from \(1\) to \(1000\) exclusive. Which means we in programming, our initial value would be \(2\) and end just before \(1000\). Then initialize sum would be \(0\) and the iteration of \(i\) will be added up continuously untill \(1000\). And then we will printf the result of sum.

So, first of all, we need to initialize our sum variable as \(0\). Then we need to use a for loop untill \(1000\) from initializing i variable as \(2\) because according to the problem, \(1\) and \(1000\) will be exclusive \((1, 1000)\). Then we will set a condition that if any \(i\) is divislbe by \(3\) or \(5\), then it will be summed up the value inside the sum variable. And then we will return sum as our answer.


#include <stdio.h>

int divisibleSum(int n);
        
int main(){
    int n = 1000;
    divisibleSum(n);
    return 0;
}

int divisibleSum(int n){
    int sum = 0;
    for(int i = 2; i < n; i++){
        if(i % 3 == 0 || i % 5 == 0){
            sum += i;
        }
    }
    printf("%d\n", sum);
    return sum;
}

Output-

 

233168


Problem 2-

The sum of the primes below \(10\) is \(2 + 3 + 5 + 7 = 17\). Find the sum of all the primes below two million. (Problem Statement)

Solve-

To solve this, it requires to know deeply about sieve-of-eratosthenes and that's it. This problem introduces us about the sieve-of-eratosthenes.


#include <stdio.h>
#include <stdbool.h>

#define N 2000000
long long COUNT = 0;
int primeSum();
int main(){
    primeSum();
    return 0;
}
int primeSum(){
    int prime[N + 1];
    for(int i = 0; i < N; i++){
        prime[i] = true;
    }
    for(int i = 2; i <= N; i++){
        if(prime[i] == true){
            for(int j = i * 2; j <= N; j += i){
                prime[j] = false;
            }
        }
    }
    for(int i = 2; i <= N; i++){
        if(prime[i] == true){
            COUNT = COUNT + i;
        }
    }
    printf("%lld\n", COUNT);
    return COUNT;
}

Output-

 

142913828922


Problem 3-

By listing the first six prime numbers: \(2, 3, 5, 7, 11\), and \(13\), we can see that the \(6\)th prime is \(13\). What is the \(10,001\)st prime number? (Problem Statement)

Solve-

This problem also involves implementing sieve of eratosthenes as previous solution. But lastly we will check \(n\)th prime number. To do that so, we will list out all the primes and then, initialize count = 0, if prime numbers meet the condition, then count++ or interate by \(1\). Lastly, if input and count are equal, terminate and print our \(n\)th prime number.


#include <stdio.h>

void prime(int n);

int main(){
    int n = 10001;
    prime(n);
    return 0;
}

void prime(int n){
    int limit = n * 20;
    int array[limit + 1];
    for(int i = 0; i <= limit; i++){
        array[i] = 1;
    }
    for(int i = 2; i <= limit; i++){
        if(array[i] == 1){
            for(int j = 2 * i; j <= limit; j += i){
                array[j] = 0;
            }
        }
    }
    int count = 0;
    for(int i = 2; i <= limit; i++){
        if(array[i] == 1){
            count++;
            if(count == n){
                printf("%d\n", i);
                return;
            }
        }
    }
}

Output-

 

104743