CODEWITHSUNDEEP
c++multithreadingoptimizationc++14
Ash
Ash

Reputation: 33

Efficiently find the nth number in a series where the numbers are only divisible by 2,3 and 5

I want to find the nth number in a series of numbers only divisible by 2, 3 and 5 and not divisible by any other primes.

Here is the simplest solution that I have for finding the 1500th number. This takes about 16 seconds to execute. I want to know if there is a way to make it any faster like maybe using multi threading.

#include <iostream>
using namespace std;

int main()
{
    int temp, seriesCounter = 1, currentNumber = 2;

    while (seriesCounter < 1500)
    {
        temp = currentNumber;

        //Remove all multiple of 2
        while (temp % 2 == 0)
        {
            temp /= 2;
        }
        //Remove all multiple of 3
        while (temp % 3 == 0)
        {
            temp /= 3;
        }
        //Remove all multiple of 5
        while (temp % 5 == 0)
        {
            temp /= 5;
        }
        // If only 1 remains, the number is valid, else not.
        if (temp == 1)
        {
            seriesCounter++;
        }
        currentNumber++;
    }

    cout << "The 1500th number in the series is : " << --currentNumber << endl << endl;

    return 1;
}

Upvotes: 0

Views: 673

Answers (2)

zhouqin
zhouqin

Reputation: 53

Fast solution done in 0.000031s on a i7 laptop (result: num[1499]=860934420):

Time complexity is O(n) (n=1500 in your case). assume the current sequence is num[]. we want to grow it to 1500 elements. the main idea is to keep a record of three locations in the sequence num[], let's call them idx[0], idx[1] and idx[3]. so that 2num[idx[0]], 3num[idx[1]], and 5*num[idx[2]] becomes just >= the last number in sequence(num.back()). then add the smallest of the three to the end of the sequence (which becomes the new num.back()).

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
using std::vector;
using namespace std::chrono;

int main()
{
    auto start = high_resolution_clock::now();
    const vector<int> p{ 2,3,5 };
    vector<int> idx{ 0,0,0 };
    vector<int> num = { 2,3,4,5 }; num.reserve(1500);
    vector<int> candidate(3);
    while (num.size() < 1500) {
        int candidate = INT_MAX;
        for (int i = 0; i < p.size(); i++) {
            int t;
            while (num.back() >= (t=num[idx[i]] * p[i])) idx[i]++;
            candidate = std::min(candidate, t);
        }
        num.push_back(candidate);
    }
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);

    std::cout << num.back();
    std::cout <<"\ntakes "<< duration.count() << " microseconds";
}

The code can further be improved. The idea is the same, but the number of multiplication performed is reduced, by remembering the multiplication result in array candidate[3]:

const vector<int> p{ 2,3,5 };
vector<int> idx{ 1,0,0 };
vector<int> num = { 2,3,4,5 }; num.reserve(1500);
vector<int> candidate{ 6,6,10 };
while (num.size() < 1500) {
    auto it = std::min_element(candidate.begin(), candidate.end());
    if (num.back() != *it) num.push_back(*it);
    int which_p = it - candidate.begin();
    *it = num[++idx[which_p]] * p[which_p];
}

Upvotes: 3

Igor Tandetnik
Igor Tandetnik

Reputation: 52481

Here's one pretty straightforward approach. It finds 1500th element in under a second (I didn't bother to measure more precisely).

#include <set>
#include <iostream>

int main() {
    int n = 1500;

    std::set<long long> s;
    s.insert(2);
    s.insert(3);
    s.insert(5);
    long long num = 0;
    while (n--) {
        num = *s.begin();
        s.erase(s.begin());
        s.insert(num*2);
        s.insert(num*3);
        s.insert(num*5);
    }
    std::cout << num;
}

Upvotes: 4

Related Questions