Thank you for your explanation and patience, mate.

I understood everything.

Hey, mate.

Could you clear up a couple of things for me?

I initialized my bitset variable by doing Primes.set();, thus making all the elements of it true. Why shouldn't I do it this way?

Why is using fill with a vector slower than using a bitset?

I didn't understand why we only have to loop until the sqrt(PRIME_LIMIT) the first time and why the conditions for your second loop were (int j = i * i; j <PRIME_LIMIT; j += step.

Thank you very much.

Petcheco

Thank you, Nathan.

Edited my code. It looks like

#include <iostream>

using namespace std;

int a = 0; int b = 0; int c = 0;

int Find_Triplet(int,int,int);

int Find_Triplet(int a, int b, int c)
{
for (a= 5; a < 500; a++)
{
    for (b = 2; b < a; b++)
    {

        c = 1000-a-b;
            if (a*a + b*b == c*c && a+b+c == 1000)
            {
                goto End_of_Loop;
            }
        }
    }

End_of_Loop:
return a*b*c;
}

int main()
{
    cout << Find_Triplet(a,b,c) << endl;
    return 0;
}

this now.

Any tips?

a can't be bigger than c.

if we have a²+b² = c², than c > b >= a.

Thank you, mate.

Thank you, sir.

Hey, guys.

Find the sum of all the primes below 2000000.

My code:

main.cpp

#include <iostream>
#include <vector>
#include <cmath>

#include "Sieve.h"

using namespace std;

typedef unsigned long long int ulli;

ulli Sum = 0;

ulli Sum_of_Primes(vector<bool>, ulli&);

ulli Sum_of_Primes(vector<bool> Primes, ulli& Sum)
{
    for(ulli a = 2; a < Upper_Limit; a++)
    {
        if (Primes[a])
        {
            Sum += a;
        }

    }
    return Sum;
}

int main()
{
    Find_Primes_until_n(Primes);
    cout << Sum_of_Primes(Primes,Sum) << endl;
    return 0;
}

Sieve.h

#ifndef SIEVE_H_INCLUDED
#define SIEVE_H_INCLUDED

using namespace std;

#define Upper_Limit 2000000

vector<bool> Primes;

void Find_Primes_until_n (vector<bool>&);

void Find_Primes_until_n(vector<bool>& Primes)
{
    Primes.resize(Upper_Limit);
    fill(Primes.begin(),Primes.begin() + Upper_Limit , true);
    for (int i = 2; i < Upper_Limit; i++)
    {
        if(Primes[i])
        {
        for (int j = 2*i; j <Upper_Limit; j+= i)
        {
             Primes[j] = false;
        }
        }
     }
}

#endif // SIEVE_H_INCLUDED

It takes about 0.3s. How can I improve it?

Thank you.

Petcheco

  • bigger than

thank you, mate.

I'll look into that.

Hey, guys.

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which, a² + b² = c².

For example, 3² + 4² = 9 + 16 = 25 = 5².

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

#include <iostream>

using namespace std;

int a = 0; int b = 0; int c = 0;
bool Found = false;

int Find_Triplet(int,int,int);

int Find_Triplet(int a, int b, int c)
{
for (int i = 5; i < 1000; i++)
{
    c = i;
    for (int j = 2; j < c; j++)
    {
        b = j;
        for (int k = 1; k < b; k++)
        {
             a = k;
            if (a*a + b*b == c*c && a+b+c == 1000)
            {
                Found = true;
                break;
            }
        }
        if (Found)
            break;
    }
    if (Found)
        break;
}
return a*b*c;
}

int main()
{
    cout << Find_Triplet(a,b,c) << endl;
    return 0;
}

How can I improve my program?

Thank you.

Petcheco

Obs.:

void Show_Prime(int);

void Show_Prime(int Wanted_Prime)
{
    cout << "The 10001-th prime is " << Wanted_Prime << endl;
}

should read

void Show_Prime(ulli);

void Show_Prime(ulli Wanted_Prime)
{
    cout << "The 10001-th prime is " << Wanted_Prime << endl;
}

Hey, guys.

I improved my code. Could you take a look at it now?

main.cpp

// A reasonable approximation is to say that the n-th prime is such that p(n) = n*(log n + log*(log n) - 1).
// With that in mind, we can say that the 10001-th prime  is smaller than 10100*(log 10100 + log(log 10100) - 1), which we can round to 105000.

#include <iostream>
#include <cmath>
#include <vector>

#include "Sieve of Eratosthenes.h"

using namespace std;

void Show_Prime(int);

void Show_Prime(int Wanted_Prime)
{
    cout << "The 10001-th prime is " << Wanted_Prime << endl;
}

int main()
{
            Find_Primes_until_n(Primes);
            Show_Prime(Wanted_Prime);

    return 0;
}

Sieve of Eratosthenes.h

#ifndef SIEVE_OF_ERATOSTHENES_H_INCLUDED
#define SIEVE_OF_ERATOSTHENES_H_INCLUDED

#define Upper_Limit 105000

using namespace std;

#define Upper_Limit 105000

typedef unsigned long long int ulli;
ulli Prime_Number = 0;
ulli Wanted_Prime = 0;

vector<bool> Primes;

ulli Find_Primes_until_n (vector<bool>);

ulli Find_Primes_until_n(vector<bool> Primes)
{
    Primes.resize(Upper_Limit);
    fill(Primes.begin(),Primes.begin() + Upper_Limit , true);
    for (ulli i = 2; i < Upper_Limit; i++)
    {
        if(Primes[i])
        {
            Prime_Number++;
        for (ulli j = 2*i; j <Upper_Limit; j+= i)
        {
             Primes[j] = false;
        }
        }
         if (Prime_Number == 10001)
        {
            Wanted_Prime = i;
            break;
        }
     }
     return Wanted_Prime;
}

#endif // SIEVE_OF_ERATOSTHENES_H_INCLUDED

Thank you.

Petcheco

Hello, guys.

How would I deal with a variable that needs to be biggers than an unsigned long long integer?

Thank you.

Up!

Check this out.

It seems to me that you have a problem on your PATH variable.

Hello.

Your buffer is probably full of garbage.

Use cin.sync() between asking for inputs and you should be good to go.

Like this:

cout << "Enter your string:";
getline(cin, myString); //line 1
cout<<"Enter your name: ";
getline(cin, myName);   //line 2
cin.sync();
cout<<"Age: ";
cin>>age;
cin.sync();

  return 0;

Kind regards,
Petcheco

Thanks, mate. I'll try and understand your code.

@rubberman

Could you explain the difference between doing what you said and what I was doing and why it's important to do what you said?

Thank you very much.

@tinstaffl

How would I implement that idea of yours? Could you provide a small code snipet?

I suppose I would have to multiply the value of the product by the number in the "i" and the number in the "i+12" position and divide by the number in the "i-1" position.

Is that correct?

Thank you.

You are definitely helping me a lot. I don't get much time to practice (going to college eats a large chunk of time) and all this help here is much appreciated.

I didn't know about that, tinstaafl. Very interesting.

Thanks for your tips.

Very good, sir. I forgot that we can use break to end a for-loop.

Thank you very much for all your help!

Hello, guys.

The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

Here's how I did it:

#include <iostream>
#include <string>
#include <vector>

using namespace std;

string Grid_of_Numbers =
"73167176531330624919225119674426574742355349194934"
"96983520312774506326239578318016984801869478851843"
"85861560789112949495459501737958331952853208805511"
"12540698747158523863050715693290963295227443043557"
"66896648950445244523161731856403098711121722383113"
"62229893423380308135336276614282806444486645238749"
"30358907296290491560440772390713810515859307960866"
"70172427121883998797908792274921901699720888093776"
"65727333001053367881220235421809751254540594752243"
"52584907711670556013604839586446706324415722155397"
"53697817977846174064955149290862569321978468622482"
"83972241375657056057490261407972968652414535100474"
"82166370484403199890008895243450658541227588666881"
"16427171479924442928230863465674813919123162824586"
"17866458359124566529476545682848912883142607690042"
"24219022671055626321111109370544217506941658960408"
"07198403850962455444362981230987879927244284909188"
"84580156166097919133875499200524063689912560717606"
"05886116467109405077541002256983155200055935729725"
"71636269561882670428252483600823257530420752963450";

vector<unsigned long int> Numbers_of_the_String(1000);
unsigned long long  int Highest_Product = 0;

void Copy_String(vector<unsigned long int>,string);
void Find_the_Highest_Product(vector<unsigned long int>);
void Show_Value(unsigned long  long int);

void Copy_String(vector<unsigned long int>, string)
{
    string Temporary_Value = "";
    for(int i = 0; i < 1000; i++)
    {
        Temporary_Value = Grid_of_Numbers[i];
        Numbers_of_the_String[i] = stoi(Temporary_Value);
    }
    Find_the_Highest_Product(Numbers_of_the_String);
}

void Find_the_Highest_Product(vector<unsigned long int> Numbers_of_the_String)
{
    unsigned long long  int Product = 1;

    for(int i = 0; i < 1000;i++)
    {

        Product = 1;
        for(int j = i; j < i+13; j++)
        {

        Product = Product * Numbers_of_the_String[j];
            if (Product == 0)
                j = i+13;
        }
         if (Product > Highest_Product)
            {
                Highest_Product = Product;
            }
    }
    Show_Value(Highest_Product);
}

void Show_Value(unsigned long long  int Highest_Product)
{
    cout << "\n\n" << Highest_Product << endl;
}

int main()
{
    Copy_String(Numbers_of_the_String, Grid_of_Numbers);
    return 0;
}

Is there a way to do this challenge without using unsigned long long integers ...

Well said, mate.

I'm programming as a hobby and it's been quite fun. The Project Euler is a remarkable tool; I'll be sure to make the most of it and improve my skills.

P.S.: This problem is actually the challenge number 07.

@ddanbe

Thanks for the tips, mate. I don't understand what

Is_Prime = i % j != 0;

is supposed to do. Could you explain?

Thank you.

@rubberman

I'll be sure to take a look on those algorithms. It seems kind of tricky. Should be fun.

Thank you, mate.

Petcheco

By adding the following piece of code: && i%16 == 0 && the program works. However, like you said, it's a very brute-force, inneficient approach.

Hello, guys.

This challenge asks us to find the 10001-th prime. Here's my code:

// A reasonable approximation is to say that the n-th prime is such that p(n) = n*(log n + log*(log n) - 1).
// With that in mind, we can say that the 10001-th prime  is smaller than 10100*(log 10100 + log(log 10100) - 1), which we can round to 105000.

#include <iostream>
#include <cmath>

#define MAX_INTERVAL 105000

using namespace std;

int Wanted_Prime = 0;

void Show_Prime(int);

void Show_Prime(int Wanted_Prime)
{
    cout << "The 10001-th prime is " << Wanted_Prime << endl;
}

int main()
{
    bool Is_Prime = true;
    int Number_of_Primes = 1;

    for (int i = 3; i < MAX_INTERVAL; i += 2)
    {
        Is_Prime = true;
        for (int j =2; j <= floor(sqrt(i)); j++)
        {
            if (i % j == 0)
            {
                Is_Prime = false;
            }
        }

        if (Is_Prime == true)
        {
            Number_of_Primes++;
        }
        if (Number_of_Primes == 10001)
        {
            Wanted_Prime = i;
            Show_Prime(Wanted_Prime);
            i = MAX_INTERVAL;
        }
    }

    return 0;
}

It takes 0.300s to run. What can I do to improve it?

Thanks.

Petcheco

Thank you, sir. I'll look into that.

But could you point out what is wrong with my code?

Petcheco

Hello, guys.

Here's the challenge:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

I wrote my code:

#include <iostream>
#include <cmath>

using namespace std;

#define MAX_VALUE 2793510720

unsigned int  Smallest_Evenly_Divisable = 0;

void Show_Number(unsigned int);

void Show_Number(unsigned int Smallest_Evenly_Divisable)
{
    cout << "\n\n" << Smallest_Evenly_Divisable << endl;
}

int main()
{
   unsigned i = 0;

    for (i = 2520; i < MAX_VALUE; i++)
    {
        if ( i % 2 == 0 && i % 3 == 0 && i % 4 == 0 && i % 5 == 0 && i % 7 == 0 && i % 8 == 0 && i % 9 == 0 && i % 11 == 0
             && i % 13 == 0 && i % 17 == 0 && i % 19 == 0)
        {
            Smallest_Evenly_Divisable = i;
            Show_Number(Smallest_Evenly_Divisable);
            i = MAX_VALUE;
        }
    }
    return 0;
}

and got 116396280 as the answer. However, the official answer is 232792560.

But here's the thing: 116396280 < 232792560 and 116396280 is evenly divisable by {1,2,3...20}.

Am I missing something? It seems to me that my answer is correct. I even created a program to do the 116396280%i, i in {1,2,3...20} operation to be sure; it checks out.

Any help would be appreciated.

Petcheco.