Problem #37 Project Euler Improvements

[RUNNER PRO AGARIO]

So I made a basic implementation for Problem #37 for Project Euler, but I absolutely hate my solution. The reason for this is because of all the header files I have to include, and because of the global variable consecutive_primes at the beginning. How may I improve this so that it is a better piece of code?

#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <chrono>
#include <string>

//Function Prototype
std::vector<long long int> primes_upto(long long int limit);

std::vector<long long int> consecutive_primes = primes_upto(1000000); //<-- Very Hard to avoid, since multiple functions need this.

std::vector<long long int> primes_upto(long long int limit)
{
    std::vector<bool> primes_bool_array (limit, true);
    std::vector <long long int> results;
    primes_bool_array[0] = primes_bool_array[1] = false;
    long long int sqrt_limit = std::sqrt(limit) + 1;
    for (long long int i = 0; i < sqrt_limit; ++i)
    {
        if (primes_bool_array[i])
        {
            for (long long int j = (2 * i); j < limit; j += i)
            {
                primes_bool_array[j] = false;
            }
        }
    }
    for (int i = 0; i < primes_bool_array.size(); ++i)
    {
        if (primes_bool_array[i])
        {
            results.push_back(i);
        }
    }
    return results;
}

bool is_trunc_prime(int number)
{
    std::vector<std::string> split_primes;
    std::string number_string = std::to_string(number);
    split_primes.push_back(number_string);
    for (int i = 1; i < number_string.size(); ++i)
    {
        split_primes.push_back(number_string.substr(0, i));
    }
    std::reverse(number_string.begin(), number_string.end());
    for (int i = 1; i < number_string.size(); ++i)
    {
        std::string temp_string = number_string.substr(0, i);
        std::reverse(temp_string.begin(), temp_string.end());
        split_primes.push_back(temp_string);
    }
    for (std::string x : split_primes)
    {
        bool is_part_prime = std::binary_search(consecutive_primes.begin(), consecutive_primes.end(), std::atol(x.c_str()));
        if (!is_part_prime) return false;
    }
    return true;
}


int main()
{
    std::chrono::time_point<std::chrono::system_clock> start = std::chrono::system_clock::now();
    bool is_prime = false;
    int num_primes = 0;
    long long int number = 9;
    long long int sum = 0;
    while (num_primes != 11)
    {
        is_prime = std::binary_search(consecutive_primes.begin(), consecutive_primes.end(), number);
        if (is_prime && is_trunc_prime(number))
        {
            ++num_primes;
            sum += number;
        }
        number += 2;
    }
    std::chrono::duration<double> elapsed_seconds = std::chrono::system_clock::now() - start;
    std::cout << "The sum of all truncatable prime numbers from right to left or left to right is " << sum << ".\n";
    std::cout << "The elapsed time was " << elapsed_seconds.count() << " seconds.\n";
}

While this is fast enough and correct, it is unclean. Thank you for your suggestions.

[TheIdeasMan]

Hi,

Just some things I noticed, not sure if it is much help.

The reason for this is because of all the header files I have to include, ...

Why is that a problem?

//<-- Very Hard to avoid, since multiple functions need this.

Send it to functions as an argument?


Use std::clock rather than system clock. The latter is a wall clock, so it isn't suitable for timing processes.

http://en.cppreference.com/w/cpp/chrono/c/clock

std::clock_t start = std::clock();


Consider using std::size_t rather than long long Also std::size_t in the for loops in conjunction with the size function, so you don't have warnings about type mismatch. The size function returns a sd::size_t

[RUNNER PRO AGARIO]

@TheIdeasMan, I don't want to send the vector as an argument to is_trunc_prime(), since copying a large vector such as that one as expensive.


Also, why is a wall clock not suitable for timing processes? In fact, I don't even know what a wall clock is...

Could you explain the differences between the two timing techniques?

[RUNNER PRO AGARIO]

I also updated my code, changing a lot of the is_trunc_prime algorithm to as follows, and making the global consecutive_primes into a const variable:

#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <string>

//Function Prototypes
std::vector<long long int> primes_upto(long long int limit);
bool is_trunc_prime(long long int number);

const std::vector<long long int> consecutive_primes = primes_upto(1000000); //Represents all the primes up to 1 million


int main()
{
    bool is_prime = false;
    int num_primes = 0;
    long long int number = 9;
    long long int sum = 0;
    std::clock_t start = clock();
    while (num_primes != 11)
    {
        is_prime = std::binary_search(consecutive_primes.begin(), consecutive_primes.end(), number);
        if (is_prime && is_trunc_prime(number))
        {
            ++num_primes;
            sum += number;
        }
        number += 2;
    }
    double elapsed_seconds = ( clock() - start ) / static_cast<double>(CLOCKS_PER_SEC);
    std::cout << "The sum of all truncatable prime numbers from right to left or left to right is " << sum << ".\n";
    std::cout << "The elapsed time was " << elapsed_seconds << " seconds.\n";
}

std::vector<long long int> primes_upto(long long int limit)
{
    //Nothing changed here
}

bool is_trunc_prime(long long int number)
{
    std::string number_string = std::to_string(number);
    for (int i = 1; i < number_string.size(); ++i)
    {
        std::string trunc_left = number_string.substr(0, i);
        std::string trunc_right = number_string.substr(i, number_string.size() - 1);
        if (!(std::binary_search(consecutive_primes.begin(), consecutive_primes.end(), std::atol(trunc_left.c_str())) 
              && 
              std::binary_search(consecutive_primes.begin(), consecutive_primes.end(), std::atol(trunc_right.c_str())))) 
        {
            return false;
        }
    }
    return true;
}

[coder777]

While this is fast enough

You don't know because of line 12. That is the most time consuming line outside your measuring.

Move consecutive_primes = primes_upto(1000000); below line 67.

By the way: The assignment is no problem time wise because it is not copied but moved.

Could you explain the differences between the two timing techniques?

The one that returns a class/struct is slower than the one returning a value only.

[RUNNER PRO AGARIO]

@coder777, I don't understand why the consecutive_primes needs to be moved below line 67. Could you elaborate on that? Sorry if I seem a bit naive, but I am just curious to why moving the statement would speed up the code. Also, instead of specifying to move the function to a line number, could you specify to which function to move it to?

[coder777]

I don't understand why the consecutive_primes needs to be moved below line 67.

Otherwise you will only see a part of the true execution time.

When you move that line of code you will surely see a significant slow down.

I am just curious to why moving the statement would speed up the code.

I think that you confuse moving a line of code with move semantic:

http://stackoverflow.com/questions/3106110/what-are-move-semantics

within the expression consecutive_primes = primes_upto(1000000); the assignment of the returned vector from primes_upto(1000000) to consecutive_primes is not time consuming because only the pointer to the values is copied not the million values.

[jlb]

I don't want to send the vector as an argument to is_trunc_prime(), since copying a large vector such as that one as expensive.

Well you can easily avoid that expensive copy if you pass the vector as a reference instead of trying to pass by value.

Also you probably should also "pre-size" your vectors instead of using push_back() if you're worried about execution time.

I also wonder if your "timer" is actually going to properly time the creation of your global vector.

This is the output I get with your last program:

The sum of all truncatable prime numbers from right to left or left to right is 748317.
The elapsed time was 0.352119 seconds.

When running the program through my IDE, I get the following total runtime: .652 seconds, which is roughly twice the time as your reported time.

[RUNNER PRO AGARIO]

How should I actually time it?

[jlb]

Move the creation of the vector into main() after you start your timer and pass it to the functions that require it as a reference parameter. You don't seem to realize that your global variable is created before anything in main() happens.

[ne555]

$ time ./a.out
The sum of all truncatable prime numbers from right to left or left to right is 748317.
The elapsed time was 0.032926 seconds.

real    0m0.053s
user    0m0.050s
sys     0m0.000s

> The elapsed time was 0.352119 seconds.
I've got 10 times less, ¿did you compile with optimizations?


> Could you explain the differences between the two timing techniques?
>> The one that returns a class/struct is slower than the one returning a value only.
¿slower how?


> Also, why is a wall clock not suitable for timing processes? In fact, I don't even know what a wall clock is...
get a clock, put it on the wall, use it to measure time.

from the manual:
(i) the elapsed real time between invocation and termination, [like using a wall clock]
(ii) the user CPU time [time spent executing instructions of the calling process.
(iii) the system CPU time [time spent in the system while executing tasks on behalf of the calling process]

your process is not the only one executing.