C++

Forum

 
large loops

zacklucky (20)
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
 
 int main(int argc, const char * argv[])
{
    int max = 28123;
    int array[100];
    // abundant numbers less than 28123
    std::vector<int> nums;
    // less than28123
    std::vector<int> allNums;
    int temp(0);
    for (int i = 0; i < max + 1; i++)
    {
        int count = 0;
        for (int j = 0; j <= i/2 +1; j++)
        {
            if ((i+1) % (j+1) == 0)
            {
                array[count] = j+1;
                count++;
            }
        }
        for (int k = 0; k < count; k++)
        {
            temp += array[k];
        }
        if (temp > i+1)
        {
            nums.push_back(i+1);
        }
        temp = 0;
        memset(array, 0, 100);
    }
    for (int i = 0; i < max; i++)
    {
        allNums.push_back(i+1);
    }
    long total(0);
// where the issue is
    for(int i = 0; i < nums.size(); ++i)
    {
        for (int j = i; j < nums.size(); ++j)
        {
            if (nums[i]+nums[j] > max)
            {
                continue;
            }
            for (int k = i+j; k < max; k++)
            {
                if (nums[i]+nums[j] == allNums[k])
                {
                    allNums[k] = 0;
                }
            }
        }
    }
    for (int i = 0; i < max; i++)
    {
        total += allNums[i];
    }
    std::cout << total << std::endl;
    return 0;
}


I need to check if two abundant numbers (numbers whose factors are bigger then themselves) add up to the numbers under 28123. Only numbers smaller than 28123 might not be the sum of two abundant numbers. I've tried to optimize the loops as best I can but the code still takes forever to run. Are there any obvious inefficiencies? Also if anybody could tell me what the O(n) is? I think it's O(n^3) but I'm not sure.
Topic archived. No new replies allowed.