-
Notifications
You must be signed in to change notification settings - Fork 0
/
prime.cpp
190 lines (160 loc) · 4.54 KB
/
prime.cpp
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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
//
// prime.cpp
//
//
// Created by truc ngo on 10/9/16.
// http://stackoverflow.com/questions/18041100/using-c-string-address-of-stack-memory-associated-with-local-variable-returned
// https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
//
#include "prime.h"
const unsigned int prime::_n = 150000;
//constructor
prime::prime() {
this->_steps = 0;
_primeArrayPtr = new unsigned int [_n];
for (unsigned int i=0; i < _n; i++) {
_primeArrayPtr[i] = 0;
}
}
//destructor
prime::~prime() {
cout << "inside destructor.." << endl;
delete [] _primeArrayPtr;
};
//return the location at i where p[i] == 0
unsigned int prime::getPrimeArraySize(unsigned int* p) {
unsigned int i = 0;
for (; i < _n; i++) {
if (p[i] == 0) {
break;
}
}
return i;
}
//printing prime-number array
void prime::printPrimeArray(bool display) {
unsigned int * p = this->_primeArrayPtr;
const unsigned int SIZE = getPrimeArraySize(p);
if (display) {
for (int i = 0; i < SIZE; i++) {
cout << "index: " << i << ", value: " << p[i] << endl;
}
}
}
/*
void prime::resizeArray() {
unsigned int * p = this->_primeArrayPtr;
const unsigned int SIZE = getPrimeArraySize(p);
unsigned int* newArr = new unsigned int [SIZE];
memcpy(newArr, p, SIZE * sizeof(int));
this->_primeArrayPtr = newArr;
}
*/
//Method #1
//Is this number a prime number?
bool prime::isPrime1(unsigned int num) {
if (num == 2) {
this->_steps++;
return true;
} else if (num == 1 || num % 2 == 0) {
this->_steps++;
return false;
}
//for numbers with value of 3 and above
for (unsigned int i = 3; (i*i) <= num; i += 2) {
this->_steps++;
if (num%i == 0) {
return false;
}
}
return true;
}
void prime::getAllPrimeNumbers1() {
int k = 0;
const unsigned int SIZE = _n;
for (unsigned int i=1; i<= SIZE; i++) {
if (isPrime1(i)) {
this->_primeArrayPtr[k++] = i;
}
}
}
//Method #2
//Is this number a prime number?
//divide input number by every prime number of the primeNumberArray
//p is pointer to primeArray
bool prime::isPrime2(unsigned int num, unsigned int* p, unsigned int indexForNextPrimeNumber) {
if (num == 2) {
this->_steps++;
p[0] = num;
} else if (num == 1 || num % 2 == 0) {
this->_steps++;
return false;
}
//p = {2,3,5,7}
//8 % 2 == 0 -> 8 is not a prime
//11 % {2,3,5,7} != 0 -> 11 is a prime
for (unsigned int i = 0; i < indexForNextPrimeNumber; i += 1) {
this->_steps++;
if (num % p[i] == 0) {
return false;
}
}
return true;
}
void prime::getAllPrimeNumbers2() {
int indexForNextPrimeNumber = 0;
const unsigned int SIZE = _n;
for (unsigned int i=1; i<= SIZE; i++) {
if (isPrime2(i, this->_primeArrayPtr, indexForNextPrimeNumber)) {
this->_primeArrayPtr[indexForNextPrimeNumber++] = i;
}
}
}
void prime::getAllPrimeNumbers3() {
const unsigned int SIZE = _n+1;
static unsigned int p[SIZE];
//fill up array with number from 2 to n
//index: 2 3 4 5 6 7 8 9 10 ...
//value: 2 3 4 5 6 7 8 9 10 ...
for (unsigned int i=0; i < SIZE; i++) {
this->_steps++;
p[i] = i;
}
p[0] = 0;
p[1] = 0;
//assign all those numbers which are not primes to zero
for (int i = 2; (i*i) <= SIZE; ++i) {
for (int j = i; (i*j) <= SIZE; ++j) {
this->_steps++;
p[i*j] = 0;
}
}
//create a new array to bin those remaining prime numbers
unsigned int k = 0;
unsigned int* newP = new unsigned int [SIZE];
for (unsigned int i = 0; i < SIZE; i += 1) {
this->_steps++;
if (p[i] != 0) {
this->_steps++;
newP[k++] = p[i];
}
}
//assign this new array back to object's prime number array
delete [] this->_primeArrayPtr;
this->_primeArrayPtr = newP;
}
/* equal operator == */
//return true if two primeNumberArray is of the same
bool prime::operator==(const prime& obj) {
unsigned int arrayLength1 = getPrimeArraySize(this->_primeArrayPtr);
unsigned int arrayLength2 = getPrimeArraySize(obj._primeArrayPtr);
bool b1 = (arrayLength1 == arrayLength2) ? true : false;
bool b2 = true;
for (unsigned int i = 0; i < arrayLength1; i++) {
if (this->_primeArrayPtr[i] != obj._primeArrayPtr[i]) {
b2 = false;
break;
}
}
return (b1 && b2);
}