How Do I determine if a number is a prime number in array that has 1000 elements in it?

Question

I am making a program that determines if a value is composite, Prime, or Unvisited. The program ignores the first two values because they are 0 and 1, and labels them as I for ignore. Instead of outputting numbers it outputs the letter representation. example: "0123456" would output "IIPPCPC". It need to determines all the values up to 1000. The program uses loops to go through the array and change the value to the correct letter that represents it. I am confused on what code I would use to loop through the array and change all the values that are set to P at the moment that are composite to C. The program is suppose to reloop through the code in steps until all the values have be set to the correct representation.

    /*
    / Name: Ralph Lee Stone
    / Description: Uses an array to find all the prime numbers up to 1000.
    / Date: 11/13/2013
    / Project: RLStone3_HW_10
    */

    #include <iostream>
    using namespace std;

    int main()
    {
// Declares an array to print all prime numbers up to 1000.
char mychararray[1001];

// Set all array index values to 'U', which stands for unvisited.
for(int i = 0; i <= 1000; i++)
{
mychararray[i] = 'U';
}

// Set the first two elements of the array index 0 & 1 to 'I'. which stands for                ignore. 
mychararray[0] = 'I';
mychararray[1] = 'I';

//for ( int i = 0 ; i < 1001 ; i ++ )
//  cout << mychararray[i] ;
//cout << mychararray;

    //Skips the first two values, so that the first two values are skipped.
int i = 0;
while(mychararray[i] !='U')
    i++;

// Changes the all the values that are set to U to P.

for(int i = 2; mychararray[i] >= mychararray[1001];  i++)
mychararray[i] = 'P';
//i++;

    // Loops through the array again and changes all the values that are set to P that are composite to C.

    // Outputs the array.
for ( int i = 0 ; i < 1001 ; i ++ )
    cout << mychararray[i] ;

//Pauses the console window.
system("pause");

// returns the value 0.
return(0);
    }

The way to determine whether a number is prime has nothing to do with the fact that you have an array of 1000 numbers. — user207421, Nov 15 '13 at 23:57
Most of this code is redundant and pointless (and will most likely be optimized away by the compiler anyway). Why set all the values to `U` if you are immediately going to change them to two `I`s followed by all `P`s? And why bother setting them to `P` if you are going to change some of them to `U`? Instead, set the first two values to `I`, then loop through the rest of the values and set each to `P` or `C` according to whether or not the value is prime or composite. The resulting code will be much cleaner. — JBentley, Nov 16 '13 at 00:27
If you really must populate the values with `U` to start with (for example because some other thread might inspect the array before you are done, and needs to know whether an element has been processed or not), then consider using `std::fill_n` (see [this answer](http://stackoverflow.com/a/1065800/1227469)). Also, this is a C++ problem, so use C++ solutions - `std::vector` instead of an array (unless your professor has specified arrays in the problem). The code you have written might as well be C. — JBentley, Nov 16 '13 at 00:37

score 4 · Answer 1 · answered Nov 15 '13 at 23:57

4

This looks a lot like homework, so I'll skip the details. What you want is called the sieve of eratosthenes and consists in takin the numbers you already know are primes and discard all their multiples from the rest of the array.

answered Nov 15 '13 at 23:57

Alexandre Araujo Moreira

477
2
9

Brian Gradin · Accepted Answer · 2013-11-16T00:02:54.453

3

for (int i = 2; i < 1001; i++)
{
    for (int j = 2; j <= (int) sqrt(i); j++)
    {
        if (i % j == 0)
        {
            mychararray[i] = 'C';
            break;
        }
    }
}

^^ For every number in the array check if the number is divisible by any numbers from 2 up to the square root of the number

for (int i = 2; i < 1001; i++)
{
    for (int j = 2; j * i < 1001; j++)
        mychararray[j * i] = 'C';
}

^^ Sieve of Eratosthenes

edited Nov 16 '13 at 00:02

answered Nov 15 '13 at 23:57

Brian Gradin

2,165
1
21
42

From 2 up to the square root of the number is all that is required. – user207421 Nov 15 '13 at 23:58
Right. Of course. Edited. – Brian Gradin Nov 15 '13 at 23:59
This will say that 6 is a prime. – Nov 16 '13 at 00:02
Good point, @hvd. Edited: Added 1 to the condition for the top example so that for i = 6, j wouldn't stop before 2. – Brian Gradin Nov 16 '13 at 00:04
You just need j <= sqrt(i) actually, it's clearer. – user207421 Nov 16 '13 at 00:05
Thank you Brian Gradin the Sieve of Eratosthenes method was what I was missing. – Ralph Lee Stone Nov 16 '13 at 00:31

score 0 · Answer 3 · answered Nov 16 '13 at 00:00

For definition, 1 is prime, 2 is the only prime number, so, you can have something like this:

bool isPrime(unsigned int number) {
    if (number == 1 || number == 2) {
        return true;
    }

    if (number % 2 == 0) {
        return false;
    }

    for (int i = 2; i < number / 2; i++) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}

Then, you iterate over you array:

char representation[SIZE];
for (int i = 0; i < SIZE; i++) {
    representation[i] = isPrime(data[i]) ? 'P' : 'C';
}

How Do I determine if a number is a prime number in array that has 1000 elements in it?

3 Answers3