big numbers, big runtime

I would still consider myself a beginner, but I was trying some of the middle Project Euler problems (at least those that looked doable for me), and I'm having problems with the puzzles involving huge numbers. Here's problem 268 as an example:

It can be verified that there are 23 positive integers less than 1000 that are divisible by at least four distinct primes less than 100.

Find how many positive integers less than 10^16 are divisible by at least four distinct primes less than 100.

I put the ^ in since 10 to the power of 16 was displaying as 1016. Anyway, I'm fairly sure my code is working, but judging from my progress markers, it's going to take about 200 years to calculate... How do I go about speeding this up? My code below:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
using namespace std;

int main()
{
    long long bignumber=1;// avoid the false positive of 0
    int primecount=0;
    long long answer=0;
    int primes[25]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};

    while (bignumber<10000000000000000) // 10^16
    {
        primecount=0;
        if (bignumber%10000000==0)// to see progress
        {
            cout << bignumber << " " << answer << endl;
        }
        for (int i=0; i<25; i++)
        {
            if (bignumber%primes[i]==0)
            {
                primecount++; // maybe I should do the division
                if (primecount==4)
                {
                    answer++;
                    break;
                }
            }
        }
        bignumber++;
    }
    cout << answer << endl;
    cin.clear(); // to view the end result;
    cin.ignore(255, '\n');
    cin.get();
    return 0;
}


I did think of a few ideas
1. Make a large array of all possible 4-prime products- impractical and surely slower.
2. Make a copy of bignumber and divide while possible, seemed ok, but was going about 2 seconds slower per 10 million.
3. Instead of using bignumber%primes[i]==0, use
1
2
long long divide=bignumber/primes[i];
if (divide*primes[i]==bignumber)
. This was marginally slower, losing about half a second per 10 million.
edit: just had a 4th idea= do the same as 3. but don't use a new variable, instead using if ((bignumber/primes[i])*primes[i]==bignumber). This seems slightly faster than the original, maybe 0.2 seconds per 10 million or something.
Last edited on
Since the brute force approach is going to take that long I doubt that tinkering with it to make it a bit faster is going to help. After all even if you manage to make it 100 times faster it still going to take far too long (2 years?). The puzzle is clearly about finding an algorithm that runs in an acceptably short amount of time.
You should probably start by having the program generate all possible combinations of products of 4 primes from the set of 25 primes under 100. There are only about 303 600 of them.
See if you can come up with a fast algorithm based around that idea.
Topic archived. No new replies allowed.