C++

Forum

 
Print out prime numbers using an array

vishivish01 (14)
I need to code a program so that it can compute all the prime numbers less than a number input by a user. Say I enter "100", the code is going to find all prime numbers from 1-99 by storing them in an array and then print them out to the screen.

I know that to test if a positive integer N is prime, one can divide N by all integers from 2 up to the square root of N. I just have no idea on how to start coding this as I'm not too familiar with arrays. Thanks.
yulingo (233)
http://www.cplusplus.com/doc/tutorial/arrays/

Keep a pointer or index to the place you last inserted into the array, and increment it every time you find a new prime number. You sound like you know how to do the prime number calculation so I assume you know how to use loops.
Chervil (7320)
Once you get a foothold with this concept, you can make use of the array as part of the testing procedure. For example, we know that it is a waste of time testing whether a number is divisible by any of the even numbers such as 4, 6 or 8. Similarly there's no need to test whether a number is divisible by 9 or 15. In fact all you need to do is show that the number is not divisible by any of the prime numbers, which the program is itself gradually adding to the array.
Garion (296)
Reading your question i don't think you would even need an array if all you want to do is print out the prime numbers.

I wrote this code here and I think it's accurate. All it does is a loop within a loop and if a number is only divisible by itself and 1 prints it out.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
 #include <iostream>

int main() {
    int user_input, x;
    std::cout << "This program will check for prime numbers\n";
    std::cout << "Please enter an integer upper bound: ";
    std:: cin >> user_input;
    //this for loop goes through each number up to the user input upper boundary
    for (int i = 2; i < user_input; i++){// i starts at 2 because the numbers 1 and 2 are by default prime numbers.
        x = 0;//a variable to check if a number is prime. If it gets set to 1 the number is not prime.
        for (int j = 2; j < i; j++){//this loop divides the number by 2 up to itself and if the remainder is 0 sets x = 1.
            if (i%j == 0){
                x = 1;
                break;
            }
        }
        if (x == 0){//if the x = 1 flag is never set the number is prime.
            std::cout << i << " is a prime number\n";
        }
    }
    return 0;
}


edit.. guess i could add some comments to explain it sec.
there put a few comments in to make it easier to understand

hmm.. it could probably be faster if i added in break
Last edited on
vishivish01 (14)
Well thanks Garion for your reply, but I need to use arrays as part of a C++ exercise.
Garion (296)
Well if you just have to store the data in an array then print only if it's prime it'd be easy enough.

If you have to store the prime numbers in a separate array then print from that array it'd be a little trickier.

I read about the .pushback() thing and it seems to work well if you need to make an array based on an unknown number of elements.

This would be an example

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
 
int main() {
    int user_input, x;
    std::vector<int> prime_vector;
    std::cout << "This program will check for prime numbers\n";
    std::cout << "Please enter an integer upper bound: ";
    std::cin >> user_input;
    int number_array[user_input];
    for (int i = (user_input - 1); i > -1; i--){
         number_array[i] = i+1;
         }
    for (int i = (user_input-1); i > -1; i--){
        x = 0;
        for (int j = i; j > 1; j--){
            if (number_array[i]%j == 0){
                x = 1;
                if (number_array[i] == 2){x = 0;}
                }
        }
        if (x == 0){//
            prime_vector.push_back ((i+1));
        }
    }
    for (int i = (int(prime_vector.size())-1) ; i > 0 ; i--){
        std::cout << prime_vector[i-1] << " is a prime number\n";
    }
    return 0;
}


if you are allowed to just print you could do a regular cout without making a prime number array though. An example might be like this. (you'd have to swap around the output if you want it to go lowest to highest.)

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
 
 #include <iostream>
 #include <vector>

int main() {
    int user_input, x;
    std::cout << "This program will check for prime numbers\n";
    std::cout << "Please enter an integer upper bound: ";
    std::cin >> user_input;
    int number_array[user_input];
    for (int i = (user_input - 1); i > -1; i--){
         number_array[i] = i+1;
         }
    for (int i = (user_input-1); i > -1; i--){
        x = 0;
        for (int j = i; j > 1; j--){
            if (number_array[i]%j == 0){
                x = 1;
                if (number_array[i] == 2){x = 0;}
                }
        }
        if (x == 0){
            std::cout << number_array[i] << " is a prime number\n";
        }
    }
    return 0;
}
Last edited on
vishivish01 (14)
I believe that my code is working pretty well. I configured it so that it only prints out 10 prime numbers per line. My code does this but there is an uneven amount of spaces between each line if the user inputs a number like 300 or more. Can someone run this so that they can see what's happening and let me know what to do.

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

void _Max_();
void prime(int);

int main()
{
    _Max_();

return 0;
}

void _Max_()
{
    int input;

    cout << "Enter the number in which you want to find all prime numbers up to: ";
    cin >> input;
    prime(input);
}

void prime(int Size)
{
    int Array[Size];
    int x = 0, endline = 0;

    for (int fillArray=0; fillArray<Size; fillArray++)
    {
        Array[fillArray] = fillArray+1;
    }

    for (int i=1; i<(Size-1); i++)
    {
        for (int j=2; j<=sqrt(i); j++)
        {
            if (Array[i]%j == 0)
            {
                x = 1;
            }
        }
        if (Array[i] == 4)
        {
            x =1;
        }
        if (x == 0)
        {
            cout << Array[i] << " ";
            endline++;
        }
        x = 0;
        if (endline%10 == 0)
        {
        cout << endl;
        }
    }

}
Last edited on
Garion (296)
That seems like a nice solution.

Your problem with the extra lines was you never reset the "endline" integer to 0 after a line was printed out.

However you would need one extra if statement to check if endline != to 0 also.

That way if endline is 0 and 0 divided by 10 equals 0 it would not print out an endl

edit.. I guess you could use a boolean AND also but that's up to you ;p

Here is the working example

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;

void _Max_();
void prime(int);

int main()
{
    _Max_();

return 0;
}

void _Max_()
{
    int input;

    cout << "Enter the number in which you want to find all prime numbers up to: ";
    cin >> input;
    prime(input);
}

void prime(int Size)
{
    int Array[Size];
    int x = 0;
    int endline = 0;

    for (int fillArray=0; fillArray<Size; fillArray++)
    {
        Array[fillArray] = fillArray+1;
    }

    for (int i=1; i<(Size-1); i++)
    {
        for (int j=2; j<=sqrt(i); j++)
        {
            if (Array[i]%j == 0)
            {
                x = 1;
                break;
            }
        }
        if (Array[i] == 4)
        {
            x =1;
        }
        if (x == 0)
        {
            cout << Array[i] << " ";
            endline = endline++;
        }
        x = 0;
        if (endline != 0){
        if (endline%10 == 0)
        {
        cout << endl;
        endline = 0;
        }
        }
    }

}
Last edited on
vishivish01 (14)
Thanks Garion for the example. Can you elaborate more on the endline

situation if you may because I still can't seem to grasp the concept of it that

you coded above. I just did a small separate example with a for loop with

the original method that I came up with and nothing weird happened.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
#include <iostream>
using namespace std;

int main()
{
    int endline = 0, j;

    for (int i=0; i<100; i++)
    {
        j = i+1;
        cout << j << " ";
        endline++;
        if (endline%10 == 0)
            cout << endl;

    }
}
Garion (296)
TL/DR: Your problem is your test program updated the endline variable every cycle whereas your prime number program does not update endline variable every cycle.

---------------------------------------------------------------------------------------------------------------------------------------

When you get into numbers greater than 100 the separation between prime numbers is larger than 2 spaces so you start running into problems.

Basically your program checks the endline divided by ten every cycle. regardless of if endline has been updated or not. So if the last cycle was a prime number and printed out an endl; but the new cycle was not a prime number... then endline would still be a multiple of ten making the endline If statement valid and print an extra endl;

It might be easier to see if you use this version of the code you posted. All i did was add an "x" to your endline cout

If you count the number of x's between the prime number at a end of a line and the prime number at the beginning of a line you will see that it is the same as the number of lines or "x's" in this case.

Like the end of row three is prime number 103. The beginning of line four is prime number 107. So there are 3 spaces because, program cycles through 104 not a prime number.. endline doesn't get updated so it's still equal to 30. 30 modulo 10 is 0 so print out an endl. then it tests 105. 105 is not prime so print out an endl. then it tests 106. 106 is not prime so it prints out an endl. then it tests 107. 107 is prime so it iterates endline and doesn't print again.

Now row 4 ends with prime number 151 and the beginning of row 5 is prime number 157. so the program would test 152, not prime, so 40 modulo 10 is 0 so print endl, 153 not prime so print endl, the same with 154, 155, 156 which all print an endl. Then 157 is prime so it iterates endline and no more endl's get printed until the next row. In that case it is 5 endl's between rows. Which is the same as the difference between the last prime number of the previous row and the first prime number of the next row.

What you need to do is reset the endline variable to zero whenever the if statement that prints the endl; is run. Then set an extra check to the print endl; if statement so it doesn't run if its equal to 0 like I had in my previous post.


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

void _Max_();
void prime(int);

int main()
{
    _Max_();

return 0;
}

void _Max_()
{
    int input;

    cout << "Enter the number in which you want to find all prime numbers up to: ";
    cin >> input;
    prime(input);
}

void prime(int Size)
{
    int Array[Size];
    int x = 0, endline = 0;

    for (int fillArray=0; fillArray<Size; fillArray++)
    {
        Array[fillArray] = fillArray+1;
    }

    for (int i=1; i<(Size-1); i++)
    {
        for (int j=2; j<=sqrt(i); j++)
        {
            if (Array[i]%j == 0)
            {
                x = 1;
            }
        }
        if (Array[i] == 4)
        {
            x =1;
        }
        if (x == 0)
        {
            cout << Array[i] << " ";
            endline++;
        }
        x = 0;
        if (endline%10 == 0)
        {
        cout << "x" << endl;
        }
    }

}
Last edited on
Chervil (7320)
Note that this code does not conform to the ISO C++ standard, and will not compile except by making use of a non-standard extension offered by some compilers:
1
2
3
4
5
 
void prime(int Size)
{
    int Array[Size]; // variable-length array not standard C++

}


A standards-compliant version might look like this:
1
2
3
4
5
6
 
void prime(int Size)
{
    int * Array = new int[Size]; // allocate memory for dynamic array

    delete [] Array; // release the memory when finished
}


Alternatively, vectors are recommended in C++ to handle dynamic arrays.
http://www.cplusplus.com/reference/vector/vector/

Edit: actually, I don't see that the array is serving any purpose whatsoever here.

The only time its content are modified is in the initialisation:
Array[fillArray] = fillArray+1;
as such, it is simply cluttering up the code, using up memory, but not adding any functionality.
Last edited on
Garion (296)
I think he said his assignment required him to use an array.

It does seem unnecessary. Glad I'm not taking a class, so I don't have to do stuff like this that doesn't make sense lol.
Chervil (7320)
Glad I'm not taking a class, so I don't have to do stuff like this that doesn't make sense lol.


I'm sure the question made sense. It is only this particular answer which does not. I think it would be better to go back to the original question and see exactly in which way the array is supposed to be used. I can think of at least two different uses for an array in finding prime numbers.
Garion (296)
Thanks for the info on arrays. I was able to set up some arrays that other way you mentioned.

The tutorial on the website probably should be updated if setting up arrays without a pointer is going to become obsolete soon.

Both the array section and the dynamic memory section show examples using the nonstandard array format and never show examples for the new standard.

http://www.cplusplus.com/doc/tutorial/arrays/
http://www.cplusplus.com/doc/tutorial/dynamic/

One downside I notice already is I can't do this to get the length of an array. I guess it doesn't work with a pointer.
(sizeof(array_name)/sizeof(array_name[0]))

I've used functions to automatically set up arrays and then that code above to figure out the number of elements for new functions so I will have to learn vectors I suppose.

So arrays are only really useful for fixed length data sequences and vectors are exclusively for variable length if I'm understanding this correctly.
Last edited on
Topic archived. No new replies allowed.