C++

Forum

 
Slow Prime, Perfect, Triangular Program.

sr2cute702 (69)
Hello,

Could you help me in making this program run faster? As it is it runs and completes in about 9 seconds. Is there a way to reduce the time with the large numbers that i'm checking?

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
 
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <iomanip>
#include <cmath>

using namespace std;

bool isPerfect(int);
bool isPerfectSquare(double);
bool isPrime(int );
bool isTriangular(int);

const int MAX = 100001;

struct number_properties
{
        int number;
        bool prime, perfect, square, triangular;
};

int main()
{
        number_properties nums[MAX];

        for(int i = 0; i < 100000; i++)
        {
                nums[i].number = i;
                nums[i].prime = isPrime(i);
                nums[i].perfect = isPerfect(i);
                nums[i].square = isPerfectSquare(i);
                nums[i].triangular = isTriangular(i);
        }

        int prm = 0, prf = 0, tri = 0, sqr = 0;

        for(int j = 0; j < 100000; j++)
        {
                if (nums[j].prime)
                        prm++;
                if (nums[j].perfect)
                        prf++;
                if (nums[j].square)
                        sqr++;
                if (nums[j].triangular)
                        tri++;
        }
        cout<<"Range 1 to 100000:"<<endl;
        cout<<'\t'<<prm<<" Prime numbers"<<endl;
        cout<<'\t'<<prf<<" Perfect numbers"<<endl;
        cout<<'\t'<<sqr<<" Square numbers"<<endl;
        cout<<'\t'<<tri<<" Triangular numbers"<<endl;

        for(int j = 0; j < 10000; j++)
        {
                if (nums[j].prime)
                        prm++;
                if (nums[j].perfect)
                        prf++;
                if (nums[j].square)
                        sqr++;
                if (nums[j].triangular)
                        tri++;
        }
        cout<<"Range 1 to 10000:"<<endl;
        cout<<'\t'<<prm<<" Prime numbers"<<endl;
        cout<<'\t'<<prf<<" Perfect numbers"<<endl;
        cout<<'\t'<<sqr<<" Square numbers"<<endl;
        cout<<'\t'<<tri<<" Triangular numbers"<<endl;

        for(int j = 0; j < 20000; j++)
        {
                if (nums[j].prime)
                        prm++;
                if (nums[j].perfect)
                        prf++;
                if (nums[j].square)
                        sqr++;
                if (nums[j].triangular)
                        tri++;
        }
        cout<<"Range 1 to 20000:"<<endl;
        cout<<'\t'<<prm<<" Prime numbers"<<endl;
        cout<<'\t'<<prf<<" Perfect numbers"<<endl;
        cout<<'\t'<<sqr<<" Square numbers"<<endl;
        cout<<'\t'<<tri<<" Triangular numbers"<<endl;

return 0;
}

bool isPerfect(int n)
{
    // To store sum of divisors
    long long int sum = 1;

    // Find all divisors and add them
    for (long long int i=2; i*i<=n; i++)
        if (n%i==0)
            sum = sum + i + n/i;

     // If sum of divisors is equal to
     // n, then n is a perfect number
     if (sum == n && n != 1)
          return true;

     return false;
}

bool isPerfectSquare(double num)
{
  // Find floating point value of
  // square root of num.
  long double sr = sqrt(num);

  // If square root is an integer
  return ((sr - floor(sr)) == 0);
}

bool isPrime(int num)
{
    // Corner case
    if (num <= 1)
        return false;

    // Check from 2 to num-1
    for (int i = 2; i < num; i++)
        if (num % i == 0)
            return false;

    return true;
}

bool isTriangular(int num)
{
    // Base case
    if (num < 0)
        return false;

    // A Triangular number must be sum of first n
    // natural numbers
    int sum = 0;
    for (int n = 1; sum<=num; n++)
   {
        sum = sum + n;
        if (sum==num)
            return true;
    }

    return false;
}
tpb (1495)
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
 
#include <iostream>
#include <cstring> // memset
using namespace std;

typedef unsigned long NumType;

const NumType MAX = 100000;

struct NumberProps {
    bool prime, perfect, square, triangular;
};

// Sieve of Eratosthenes
void checkPrimes(NumberProps *nums) {
    nums[0].prime = nums[1].prime = false;
    // Start with all prime
    for (NumType i = 2; i <= MAX; i++)
        nums[i].prime = true;
    // Cross out multiples of 2
    for (NumType i = 4; i <= MAX; i += 2)
        nums[i].prime = false;

    NumType i = 1;
    while (true) {
        // Find next prime
        while (true) {
            i += 2;
            if (i * i > MAX)
                return;
            if (nums[i].prime)
                break;
        }
        // Cross out its multiples
        for (NumType j = i + i; j <= MAX; j += i)
            nums[j].prime = false;
    }
}

// Triangular numbers are sums of positive integers
void checkTriangulars(NumberProps *nums) {
    NumType sum = 0;
    for (NumType n = 1; sum <= MAX; n++) {
        nums[sum].triangular = true;
        sum += n;
    }
}

// Squares are sums of odd integers
void checkPerfectSquares(NumberProps *nums) {
    NumType sum = 1;
    for (NumType n = 3; sum <= MAX; n += 2) {
        nums[sum].square = true;
        sum += n;
    }
}

//Since there are only 8 perfect numbers that fit into 64 bits
//it seems reasonable to just enumerate them:
//6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128
void checkPerfects(NumberProps *nums) {
    nums[6].perfect = true;
    nums[28].perfect = true;
    nums[496].perfect = true;
    nums[8128].perfect = true;
    if (MAX > 33550336)
        nums[33550336].perfect = true;
}

void print(int max, int prm, int prf, int tri, int sqr) {
    cout<<"Range 1 to " << max << ":\n";
    cout<<'\t'<<prm<<" Prime numbers\n";
    cout<<'\t'<<prf<<" Perfect numbers\n";
    cout<<'\t'<<sqr<<" Square numbers\n";
    cout<<'\t'<<tri<<" Triangular numbers\n\n";
}

int main() {
    static NumberProps nums[MAX + 1];
    memset(nums, 0, sizeof nums);  // start all bools as false

    checkPrimes(nums);
    checkTriangulars(nums);
    checkPerfects(nums);
    checkPerfectSquares(nums);

    NumType prm = 0, prf = 0, tri = 0, sqr = 0;

    for(NumType i = 0; i <= MAX; i++) {
        if (nums[i].prime)
            prm++;
        if (nums[i].perfect)
            prf++;
        if (nums[i].square)
            sqr++;
        if (nums[i].triangular)
            tri++;
        if (i == 10000)
            print(10000, prm, prf, tri, sqr);
        else if (i == 20000)
            print(20000, prm, prf, tri, sqr);
    }
    print(MAX, prm, prf, tri, sqr);

    return 0;
}

It does MAX = one hundred million in 4 or 5 seconds.
Last edited on
sr2cute702 (69)
Could you help me fix my display and counter void functions?

here is the error the compliler gave. 


FNL.cpp: In function ‘int main()’:
FNL.cpp:43:11: error: storage size of ‘num’ isn’t known
  bool num[];
           ^
FNL.cpp: In function ‘void counter(int*, bool*, int&, int&, int&, int&, int, int)’:
FNL.cpp:123:28: error: request for member ‘prime’ in ‘*(num + ((sizetype)j))’, which is of non-class type ‘bool’
                 if (num[j].prime)
                            ^
FNL.cpp:125:28: error: request for member ‘perfect’ in ‘*(num + ((sizetype)j))’, which is of non-class type ‘bool’
                 if (num[j].perfect)
                            ^
FNL.cpp:127:28: error: request for member ‘square’ in ‘*(num + ((sizetype)j))’, which is of non-class type ‘bool’
                 if (num[j].square)
                            ^
FNL.cpp:129:28: error: request for member ‘triangular’ in ‘*(num + ((sizetype)j))’, which is of non-class type ‘bool’
                 if (num[j].triangular)
                            ^
FNL.cpp: At global scope:
FNL.cpp:117:6: error: unused parameter ‘nums’ [-Werror=unused-parameter]
 void counter(int nums[], bool num[], int& prm, int& prf, int& sqr, int& tri, int start, int end)



here is the code i have so far. 

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
 
#include <iostream>
#include <cmath>

using namespace std;

bool isPerfect(int);
bool isPerfectSquare(double);
bool isPrime(int );
bool isTriangular(int);
void counter(int[], bool[], int&, int&, int&, int&, int, int);
void display(int, int, int, int, int, int);

const int MAX = 100001;

struct number_properties
{
        int number;
        bool prime, perfect, square, triangular;
};

int main()
{
        number_properties nums[MAX];

        for(int i = 0; i < MAX; i++)
        {
                nums[i].number = i;
                nums[i].prime = isPrime(i);
                nums[i].perfect = isPerfect(i);
                nums[i].square = isPerfectSquare(i);
                nums[i].triangular = isTriangular(i);
        }

        int prm = 0, prf = 0, tri = 0, sqr = 0;
        int start = 1, end = 100000;
        bool num[];

        counter(nums, num, prm, prf, sqr, tri, start, end);
        display(prm, prf, sqr, tri, start, end);

return 0;

}
//This check if a number is perfect
// if it is it will evaluate to true.
bool isPerfect(int n)
{
    // To store sum of divisors
    long long int sum = 1;

    // Find all divisors and add them
    for (long long int i=2; i*i<=n; i++)
        if (n%i==0)
            sum = sum + i + n/i;

     // If sum of divisors is equal to
     // n, then n is a perfect number
     if (sum == n && n != 1)
          return true;

     return false;
}
//This checks if the number is a 
// perfect square, if so it will
//evaluate to true. 
bool isPerfectSquare(double num)
{
  // Find floating point value of
  // square root of num.
  long double sr = sqrt(num);

  // If square root is an integer
  return ((sr - floor(sr)) == 0);
}
//This checks if the number is prime
//if so it will evaluate to true.
bool isPrime(int num)
{
    // Corner case
    if (num <= 1)
        return false;

    // Check from 2 to num-1
    for (int i = 2; i < num; i++)
        if (num % i == 0)
            return false;

    return true;
}
//This checks if the number is 
//triangular if so it will eval to true.
bool isTriangular(int num)
{
    // Base case
    if (num < 0)
        return false;

    // A Triangular number must be sum of first n
    // natural numbers
    int sum = 0;
    for (int n = 1; sum<=num; n++)
    {
        sum = sum + n;
        if (sum==num)
            return true;
    }

    return false;
}
void counter(int nums[], bool num[], int& prm, int& prf, int& sqr, int& tri, int start, int end)
{
        //int prm = 0, prf = 0, tri = 0, sqr = 0;

        for(int j = start; j < end; j++)
        {
                if (num[j].prime)
                        prm++;
                if (num[j].perfect)
                        prf++;
                if (num[j].square)
                        sqr++;
                if (num[j].triangular)
                        tri++;
        }

}
void display( int prm, int prf, int sqr, int tri, int low, int high)
{
        cout<<"Range "<<low<<" to "<<high<<":"<<endl;
        cout<<'\t'<<prm<<" Prime numbers"<<endl;
        cout<<'\t'<<prf<<" Perfect numbers"<<endl;
        cout<<'\t'<<sqr<<" Square numbers"<<endl;
        cout<<'\t'<<tri<<" Triangular numbers"<<endl;
}
Topic archived. No new replies allowed.