C++

Forum

 
Finding prime numbers of an array of integers

chalupabatman (16)
I am trying to get my program to work and I think I got it pretty good the only part that I am having issues with is getting the array to display the correct prime numbers. I have ran the program and it seems to find all the correct prime numbers. Here is the instructions:

Display a title, then ask the user to specify a range of positive integers with a low and high boundary. For each entry, repeat until the user enters a positive number. After a positive high boundary has been entered, test for low boundary less than or equal to the high boundary and if it is not repeat the process. After you find the prime numbers display them with the boundaries.

-1 means not prime (crossed out)
+1 means prime (circled)
0 means unknown

Five required functions:

(a) Given an integer size, return an array of integers of that size, with all elements initialized to zero, except for elements at indexes 0 and 1, that are set to 'Not prime' (-1) (use the 'return' statement to return the new array)

(b) Given an array of integers, and the size of that array, return the index of the first element that contains a zero. (Use the 'return' statement)

(c) Given an array of integers, the size of that array, and an integer factor, 'circle' the element at the index equal to the given factor (store +1 there), then scan the rest of the array and 'cross out' (mark with -1) every other element with an index that is a multiple of the given factor.

(d) Given an array of integers, and the size of that array, scan the array and convert every element that contains a zero (unknown) to a +1 (circled).

(e) Given an array of integers, and the size of that array, return another array of integers that contains the indexes of the elements in the first array that are 'circled' (contains +1), and also return the size of that second array. (Use the 'return' statement to return the new array, and use the reference parameter to return the array's size).

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
 
#include <iostream>
#include <math.h>
using namespace std;

int *initializeArray(int size);
int zeroElement(int tempArray[], int size);
void factorArray(int tempArray[], int size, int factor);
void scanArray(int tempArray[], int size);
int *loadNewArray(int tempArray[], int size, int &count);

int main()
{
	int low_Bound, high_Bound, first_zero, count = 0;
	int *mainArray, *secondArray;
	char again;

	cout << "The Sieve of Eratosthenes" << endl << endl;

	do
	{
		do
		{
			do
			{
				cout << "Enter the high boundary for the range of positive integers: " << endl;
				cin >> high_Bound;

				if (high_Bound <= 0)
				{
					cout << "High bound must be positive" << endl;
				}
			} while (high_Bound <= 0);

			do
			{
				cout << "Enter the low boundary for the range of positive integers: " << endl;
				cin >> low_Bound;

				if (low_Bound <= 0)
				{
					cout << "Low boundary must be positive" << endl;
				}
			} while (low_Bound <= 0);

			if (low_Bound > high_Bound)
			{
				cout << "The low boundary must be smaller than the high boundary" << endl;
			}
		} while (low_Bound > high_Bound);

		mainArray = initializeArray(high_Bound);

		first_zero = zeroElement(mainArray, high_Bound);

		factorArray(mainArray, high_Bound, first_zero);

		scanArray(mainArray, high_Bound);

		secondArray = loadNewArray(mainArray, high_Bound, count);

		cout << "The prime numbers in your range is: " << endl;

		for (int i = 0; i <= count; i++)
		{
			cout << secondArray[i] << endl;
		}

		cout << "Would you like to test another range of integers (y/n): " << endl;
		cin >> again;

	} while (again != 'n');

	return 0;
}

// (a)
int *initializeArray(int size)
{
	int *tempArray = new int[size];

	for (int i = 0; i < size; i++)
	{
		if (i == 0)
		{
			tempArray[i] = -1;
		}
		else if (i == 1)
		{
			tempArray[i] = -1;
		}
		else
		{
			tempArray[i] = 0;
		}
	}

	return tempArray;
}

// (b)
int zeroElement(int tempArray[], int size)
{
	int zero_position = -1, i = 0;

	do
	{
		if (tempArray[i] == 0)
		{
			zero_position = i;
		}

		i++;
	} while (zero_position == -1);

	return zero_position;
}

// (c)
void factorArray(int tempArray[], int size, int factor)
{
	tempArray[factor] = 1;

	for (int i = factor * 2; i < size; i += factor)
	{
		tempArray[i] = -1;
	}
}

// (d)
void scanArray(int tempArray[], int size)
{
	for (int i = 0; i < size; i++)
	{
		if (tempArray[i] == 0)
		{
			tempArray[i] = 1;
		}
	}
}

// (e)
int *loadNewArray(int tempArray[], int size, int &count)
{
	int j = 0;
	count = 0;

	for (int i = 0; i < size; i++)
	{
		if (tempArray[i] == 1)
		{
			count++;
		}
	}

	int *temp = new int[count];

	for (int i = 0; i < size; i++)
	{
		if (tempArray[i] == 1)
		{
			temp[j] = i;

			j++;
		}
	}

	return temp;
}


Also if (c) is running correctly I am getting returns that look like first run:

9594898468
-486918638
3
418994893
5
4896489341

second run:

9594898468
-486918638
3
418994893
5
4896489341
7
-189948364
9
-848948348
11

third run:

9594898468
-486918638
3
418994893
5
4896489341
7
-189948364
9
-848948348
11
-489483848
13
9594898468
-486918638
9594898468
-486918638
8486483488

And this run is with a high boundary of 15 and a low boundary of 1. This makes me think that the (e) function is not working correctly by returning the array of ints back correctly

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
    // (e)
int *loadNewArray(int tempArray[], int size, int &count)
{
	for (int i = 0; i <= size; i++)
	{
		if (tempArray[i] == 1)
		{
			count++;
		}
	}

	int *temp = new int[count];

	for (int i = 0; i <= count; i++)
	{
		if (tempArray[i] == 1)
		{
			temp[i] = i;
		}
	}

	return temp;
}


These are the only two areas that I am having trouble with any help would be awesome.. Thanks in advance
Last edited on
cire (8284)
In main when you do:
1
2
3
 
		mainArray = new int[size];

		mainArray = initializeArray(size);
you are leaking memory. First, you set mainArray to point to dynamically allocated memory which you allocate in main, then you lose the address assigned to mainArray when you set mainArray to point to dynamically allocated memory which is allocated in initializeArray.


In (b) zeroElement if there is no 0 in the array, you access outside the bounds of the array, causing undefined behavior. The requirements don't say what zeroElement should return when there are no zeros in the array.


(c) factorArray could be written more efficiently. There is no reason for a modulus or division operation in the function.

For instance:

1
2
3
4
5
6
7
8
 
void factorArray(int tempArray[], int size, int factor)
{
    // avoid special cases related to the index inside the for loop.
    tempArray[factor] = 1 ;

    for ( int i = factor * 2; i < size; i += factor )
        tempArray[i] = -1 ;
}



(d) scanArray: This function makes no sense to me in the context of a sieve. If 1 indicates a prime number, why would you indiscriminately mark "unknown" numbers as "prime"? Are you sure the description for this function has been correctly relayed here? It would make more sense if scanArray were to "scan" the array using zeroElement and factorArray to eliminate all of the zeros in the sieve.


(e) loadNewArray accesses outside the bounds of tempArray in the first loop, and the second loop is just plain wrong. Every element of temp should be assigned an index (and again temp[i] when i is equal to count is out of the bounds of the array.)
Last edited on
chalupabatman (16)
thanks for the reply!

I was looking through the code.. and would it be wise for me to just send the high boundary to the functions allowing a for loop to be like this:

 
 
for (int i = 0; i < high_Bound; i++)


Would this solve the out of bounds of the array? Instead of doing this portion in the main code

 
 
size = high_Bound - low_Bound;


for (d) I re-read it and it says exactly what I wrote up top. So I am unsure why I would change all unknowns to 1 in scanArray.

I am still working on (e) to see if I can fix the issues.
cire (8284)
The lower bound only has to do with output. You shouldn't consider it all while you're making the sieve. The size of the sieve should be high_Bound+1 if high_Bound is meant to be inclusive.

However, the problem in loadNewArray with out of bounds access is because the loop condition is wrong. You should be using a less than and not a less than or equal to comparison in that condition. The same is true in all of your functions.

Remember that an array of size elements can be indexed by 0 to size-1. size, itself, will be outside the bounds of an array if used as an index.
chalupabatman (16)
so I changed all the bounds in loops to be less than and not less than or equal to.. so the bounds seem to be correct.. I have seen that all of the functions are working now but the only one that I have seen issues with was the (e) again but the only issue that is coming up is that it just has an additional count so I am getting 7 results instead of 6 when I go from 1-15 so I just subtracted one from the count.. the new code looks like

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
 
// (e)
int *loadNewArray(int tempArray[], int size, int &count)
{
	int j = 0;

	for (int i = 0; i < size; i++)
	{
		if (tempArray[i] == 1)
		{
			count++;
		}
	}

	count--;

	int *temp = new int[count];

	for (int i = 0; i < size; i++)
	{
		if (tempArray[i] == 1)
		{
			temp[j] = i;

			j++;
		}
	}

	return temp;
}


I have another question the user has the option to do another range of integers but when I test it and say yes I do want to test another range.. All of the old prime numbers are on there and it seems the array just expands and keeps expanding.. How can I solve this so that every time I run the program with a different range of numbers the arrays reset?

this is what the output looks like:

range: 1-15
2
3
5
7
9
11
13

range: 1-20
2
3
5
7
9
11
13
15
17
19
-842150451
-842150451
-842150451
-842150451
-842150451

range: 1-20
2
3
5
7
9
11
13
15
17
19
-842150451
-842150451
-842150451
-842150451
-842150451
-842150451
-842150451
-842150451
-842150451
-842150451
-842150451
-842150451
-842150451
-842150451
-842150451

range: 1-15
2
3
5
7
9
11
13
-842150451
-842150451
-842150451
-842150451
-842150451
-842150451
-842150451
-842150451
-842150451
-842150451
-842150451
-842150451
-842150451
-842150451
-842150451
-842150451
-842150451
-842150451
-842150451
-842150451
-842150451
-842150451
-842150451
-842150451


so yeah it just keeps expanding.. also for the prime numbers.. 9 and 15 keep coming up which aren't they prime? Thanks again for the help
cire (8284)
the new code looks like
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
 
// (e)
int *loadNewArray(int tempArray[], int size, int &count)
{
	int j = 0;
   	count = 0;

	for (int i = 0; i < size; i++)
	{
		if (tempArray[i] == 1)
		{
			count++;
		}
	}

	count--;

	int *temp = new int[count];

	for (int i = 0; i < size; i++)
	{
		if (tempArray[i] == 1)
		{
			temp[j] = i;

			j++;
		}
	}

	return temp;
}


Note lines 5 and 15.

If you have numbers coming up that aren't prime, the most likely culprit is a logic problem in factorArray. I suspect you've made enough changes to your code at this point that commenting on the code in the OP won't be terribly constructive.
chalupabatman (16)
all updated
Topic archived. No new replies allowed.