A program to find prime numbers and set them into a new array

Saman2440 (3)
Hi. i wanted to make a program that finds prime numbers in an array that user gives it and put them into a new 2*n array that contains prime numbers that are found and their frequencies. for example:
user enters:
1 2 3 7 4 8 3 6 8 7 7
The result is:
3 7 2
2 3 1

but after i put in the elements it stops working. it doesn't return 0 or anything it doesn't revive any more values ether.
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
 
#include <iostream>

using namespace std;

int cp(int num){
    if (num <= 1){
        return 0;}
    for (int j = 2; j <= num/2; j++){
      if (num % j == 0){
        return 0;
      }
      else{
        return 1;
      }
    }
}
    
int main()
{
    int x, arr[x], i ,j ,r=0 ,c=0 ,parr[x] ,farr[c+1][2];
    
    cin>>x;
    cout<<"Enter Array Elements: "<<endl;
    for(i=0; i<x; i++){
        cin>>arr[i];
    }
    for(i=0; i<x; i++){
        r=cp(arr[i]);
        if(r==1)
            parr[c]=arr[i];
            c++;
    }
    for(i=0; i<c+1; i++){
        farr[i][2]=1;
    } 
    for(i=0; i<c+1; i++)                      
        for(j=0; j<c+1; j++){
            if(parr[i]==farr[j][1]){
                farr[j][2]++;
                j--;
            }
            else{
                parr[i]=farr[j][1];
            }
        }
    cout<<"The Prime Numbers: "<<endl;
    for(i=0; i<c+1; i++){
        cout<<farr[i][1]<<" ";    
    }
    for(i=0; i<c+1; i++){
        cout<<farr[i][2]<<" ";
    }
    return 0;
}
Last edited on
Ganado (6849)
Focus on one part of your program at a time, and test it before adding more to the program.

For example, start with just:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
// Example program
#include <iostream>
using namespace std;

int main()
{
    int x, arr[x];
    
    cin>>x;
    cout<<"Enter Array Elements: "<<endl;
    for(int i=0; i<x; i++){
        cin>>arr[i];
    }
    
    for(int i = 0; i < x; i++)
    {
        cout << arr[i] << '\n';   
    }
}

This unfortunately is already wrong (although might compile on gcc). When you declare your array, arr[x], the value of x at that point is not defined. Furthermore, the size of a C-style array needs to be a compile-time constant.

You either need to use a dynamic array like a vector, or use an array with a large enough max size.
e.g.
int arr[1000];

Second, let's take a look at just your prime function in isolation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
// Example program
#include <iostream>
using namespace std;

int is_prime(int num){
    if (num <= 1){
        return 0;}
    for (int j = 2; j <= num/2; j++){
      if (num % j == 0){
        return 0;
      }
      else{
        return 1;
      }
    }
}

int main()
{
    for (int i = 0; i < 20; i++)
    {
        std::cout << i << " : " << is_prime(i) << '\n';   
    }
}


0 : 0
1 : 0
2 : 0
3 : 0
4 : 0
5 : 1
6 : 0
7 : 1
8 : 0
9 : 1
10 : 0
11 : 1
12 : 0
13 : 1
14 : 0
15 : 1
16 : 0
17 : 1
18 : 0
19 : 1

Notice anything? Starting at i = 4, your algorithm is essentially just an "is_odd" function, not an "is_prime" function. This is because you are ALWAYS returning either a 0 or a 1 after the first iteration, when j = 2 in your cp function.
PS: What happens when num == 3?

____________________________________

Other things:
- you have the same issue with your parr array, and a similar issue with your farr array.
c=0, farr[c+1][2];
The size of your farr array is [1][2], regardless of what you later change c to be.

1
2
3
4
5
6
 
   for(i=0; i<x; i++){
        r=cp(arr[i]);
        if(r==1)
            parr[c]=arr[i];
            c++;
    }

Your indentation here is misleading. The c++ line is not a part of your if statement.

farr[j][2]++;
Regardless of the value of j, this is going out of bounds because the valid inner array indices are only 0 and 1 (the size of that dimension is 2).

I would re-write your code and just start small. Focus first on simply getting and saving correct user input, then focus on how to tell if a number is prime, then focus on the second array that stores pairs of numbers.
Last edited on
Saman2440 (3)
wow i didn't think i could be so wrong. This is kind of my first day in c++ so i thought its this simple XD thanks a lot i work on it. is there a complete version on this code that i can see and learn from?
Ganado (6849)
For the first day in C++, you're doing fine! Really.
I don't feel like just completing the assignment, but I suggest:
- taking it one piece at a time (e.g. just focus on getting the prime number function to work)
- try to fix your code based on the suggestions people give, and ask us what is wrong if you still can't get it to work

For the pairs of {primes, occurances}, like I said you can just use an array with some maximum allowed size.

I'll show an example that uses odd numbers instead of primes
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
 
// Example program
#include <iostream>
#include <string>
using std::cout;
using std::cin;

bool is_odd(int n)
{
    return (n % 2 != 0);   
}

const int MaxSize = 1000;

void add_number_if_odd(int number, int odd_numbers_tally[][2], int& size)
{
    if (!is_odd(number))
    {
        return;
    }
    
    // find if number already exists in array
    // If it does, increment occurrence count
    for (int i = 0; i < size; i++)
    {
        if (odd_numbers_tally[i][0] == number)
        {
            // number already exists, increment count
            odd_numbers_tally[i][1]++;
            return;
        }
    }
    
    // At this point, we know it's a new odd number
    
    if (size == MaxSize)
    {
        cout << "Error: buffer full\n";
        return;
    }
    
    // add new entry to array, increment size of array
    odd_numbers_tally[size][0] = number;
    odd_numbers_tally[size][1] = 1;
    size++;
}


int main()
{
    cout << "How many numbers will you enter? ";
    int total_count;
    cin >> total_count;
        
    // first entry: number, second entry: occurrences
    int num_odd_numbers = 0;
    int odd_numbers_tally[MaxSize][2] {};

    for (int i = 0; i < total_count; i++)
    {
        int number;
        cout << "Enter number " << (i + 1) << ": ";
        cin >> number;
        
        if (!cin)
        {
            cout << "Unexpected input\n";
            return 1;
        }
        
        // User has entered number, now need to add it to our tally
        add_number_if_odd(number, odd_numbers_tally, num_odd_numbers);            
    }
    
    // print results
    for (int i = 0; i < num_odd_numbers; i++)
    {
        int number = odd_numbers_tally[i][0];
        int count = odd_numbers_tally[i][1];
        std::cout << "Odd number: " << number << ", count: " <<  count<< '\n';
    }

    return 0;
}

How many numbers will you enter? 6        
Enter number 1: 5                                                   
Enter number 2: 7                                               
Enter number 3: 5                                                              
Enter number 4: 8                                                                
Enter number 5: 2                                                            
Enter number 6: 5                                                     
Odd number: 5, count: 3                                                              
Odd number: 7, count: 1


Your task is actually harder than most first-time beginner tasks, unless you take a shortcut like using a std::map, then it's easy.
Last edited on
Saman2440 (3)
Alright i tried to make a function that checks prime numbers and pretty much did the same things you did here for odd numbers, on prime numbers. also tried to make spacing and names a little better. But it... doesn't do what i think it should and have know idea why. frist of all it doesn't only print prime numbers but all numbers. 2nd, after i enter a number, it gets an other entry too but doesn't affect anything.
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
 
#include <iostream>

using namespace std;

int is_prime(int n)
{
    int x, r;
    cin>>n;
    if(n<=1){
        return 0;
    }
    else if(n==2){
        return 1;
    }
    else{
        for(x=2; x<n; x++){
            if(n%x==0){
                return 0;
                break;
            }
            else{
                return 1;
            }
        }
    }
}

    int MaxSize = 1000;

void add_number_if_prime(int number, int prime_numbers_array[][2], int& size)
{
    for (int i = 0; i < size; i++){
        if (prime_numbers_array[i][0] == number){
            prime_numbers_array[i][1]++;
            return;
        }
    }
    if (size == MaxSize){
        cout << "Error: buffer full\n";
        return;
    }
    prime_numbers_array[size][0] = number;
    prime_numbers_array[size][1] = 1;
    size++;
}

int main()
{
    int total_count;
    cout << "How many numbers will you enter? ";
    cin >> total_count;
    int num_prime_numbers = 0;
    int prime_numbers_array[MaxSize][2];
    for (int i = 0; i < total_count; i++){
        int number;
        cout << "Enter number " << (i + 1) << ": ";
        cin >> number;
        if (!cin){
            cout << "Unexpected input\n";
            return 1;
        }
        if(is_prime(number==1)){
        add_number_if_prime(number, prime_numbers_array, num_prime_numbers);
        }
    }
    for (int i = 0; i < num_prime_numbers; i++){
        int number = prime_numbers_array[i][0];
        int count = prime_numbers_array[i][1];
        std::cout << "Prime number: " << number << ", count: " <<  count<< '\n';
    }
    return 0;
}
seeplus (6628)
There's issues with is_prime. You need to continue the loop until the end unless the mod division is 0 in which case the number is prime. Also all even numbers are not prime, so this can be dealt with first. As only odd numbers can be prime, start the loop at 3 and inc by 2. The maximum divisor to test is sqrt(n) as larger numbers cannot be a factor.

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
 
include <iostream>
#include <cmath>
using namespace std;

constexpr size_t MaxSize {1000};

bool is_prime(int n)
{
	if ((n <= 2) || (n % 2 == 0))
		return n == 2;

	for (size_t x = 3, e = std::sqrt(n); x <= e; x += 2)
		if (n % x == 0)
			return false;

	return true;
}

void add_number_if_prime(int number, size_t prime_numbers_array[][2], size_t& size)
{
	for (size_t i = 0; i < size; ++i)
		if (prime_numbers_array[i][0] == number) {
			++prime_numbers_array[i][1];
			return;
		}

	if (size == MaxSize) {
		cout << "Error: buffer full\n";
		return;
	}

	prime_numbers_array[size][0] = number;
	prime_numbers_array[size][1] = 1;
	++size;
}

int main()
{
	size_t total_count {};

	cout << "How many numbers will you enter? ";
	cin >> total_count;

	size_t num_prime_numbers {};
	size_t prime_numbers_array[MaxSize][2] {};

	for (size_t i = 0; i < total_count; ++i) {
		int number {};

		cout << "Enter number " << (i + 1) << ": ";
		cin >> number;

		if (!cin) {
			cout << "Unexpected input\n";
			return 1;
		}

		if (is_prime(number))
			add_number_if_prime(number, prime_numbers_array, num_prime_numbers);
	}

	for (size_t i = 0; i < num_prime_numbers; ++i)
		std::cout << "Prime number: " << prime_numbers_array[i][0] << ", count: " << prime_numbers_array[i][1] << '\n';
}


Just ask if you don't understand anything.


How many numbers will you enter? 11
Enter number 1: 1
Enter number 2: 2
Enter number 3: 3
Enter number 4: 7
Enter number 5: 4
Enter number 6: 8
Enter number 7: 3
Enter number 8: 6
Enter number 9: 8
Enter number 10: 7
Enter number 11: 7
Prime number: 2, count: 1
Prime number: 3, count: 2
Prime number: 7, count: 3

Last edited on
Topic archived. No new replies allowed.