Finding composite numbers

Question

I have a range of random numbers. The range is actually determined by the user but it will be up to 1000 integers. They are placed in this:

vector<int> n

and the values are inserted like this:

srand(1);

for (i = 0; i < n; i++)
  v[i] = rand() % n;

I'm creating a separate function to find all the non-prime values. Here is what I have now, but I know it's completely wrong as I get both prime and composite in the series.

void sieve(vector<int> v, int n)
{
  int i,j;

  for(i = 2; i <= n; i++)
     {
        cout << i << " % ";
        for(j = 0; j <= n; j++)
           {
              if(i % v[j] == 0)
                 cout << v[j] << endl;
           }
     }
}

This method typically worked when I just had a series of numbers from 0-1000, but it doesn't seem to be working now when I have numbers out of order and duplicates. Is there a better method to find non-prime numbers in a vector? I'm tempted to just create another vector, fill it with n numbers and just find the non-primes that way, but would that be inefficient?

Okay, since the range is from 0-1000 I am wondering if it's easier to just create vector with 0-n sorted, and then using a sieve to find the primes, is this getting any closer?

void sieve(vector<int> v, BST<int> t, int n)
{
  vector<int> v_nonPrime(n);
  int i,j;
  for(i = 2; i < n; i++)
      v_nonPrime[i] = i;

  for(i = 2; i < n; i++)
     {

        for(j = i + 1; j < n; j++)
           {
              if(v_nonPrime[i] % j == 0)
                 cout << v_nonPrime[i] << endl;
           }
     }
}

Answer 1

You should try using a prime sieve. You need to know the maximal number for creating the sieve (O(n)) and then you can build a set of primes in that range (O(max_element) or as the problem states O(1000) == O(1))) and check whether each number is in the set of primes.

Answer 2

Basically, you have a lot of unrelated numbers, so for each one you will have to check if it's prime.

If you know the range of the numbers in advance, you can generate all prime numbers that can occur in that range (or the sqrt thereof), and test every number in your container for divisibility by any one of the generated primes.

Generating the primes is best done by the Erathostenes Sieve - many examples to be found of that algorithm.

Answer 3

First off, I think Knuth said it first: premature optimization is the cause of many bugs. Make the slow version first, and then figure out how to make it faster.

Second, for your outer loop, you really only need to go to sqrt(n) rather than n.

Answer 4

The idea of the sieve that you try to implement depends on the fact that you start at a prime (2) and cross out multitudes of that number - so all numbers that depend on the prime "2" are ruled out beforehand.

That's because all non-primes can be factorized down to primes. Whereas primes are not divisible with modulo 0 unless you divide them by 1 or by themselves.

So, if you want to rely on this algorithm, you will need some mean to actually restore this property of the algorithm.

Answer 5

In this code:

if(i % v[j] == 0)
  cout << v[j] << endl;

You are testing your index to see if it is divisible by v[j]. I think you meant to do it the other way around, i.e.:

if(v[j] % i == 0)

Right now, you are printing random divisors of i. You are not printing out random numbers which are known not to be prime. Also, you will have duplicates in your output, perhaps that is ok.

Answer 6

Your code is just plain wrong. First, you're testing i % v[j] == 0, which is backwards and also explains why you get all numbers. Second, your output will contain duplicates as you're testing and outputting each input number every time it fails the (broken) divisibility test.

Other suggestions:

Using n as the maximum value in the vector and the number of elements in the vector is confusing and pointless. You don't need to pass in the number of elements in the vector - you just query the vector's size. And you can figure out the max fairly quickly (but if you know it ahead of time you may as well pass it in).

As mentioned above, you only need to test to sqrt(n) [where n is the max value in the vecotr]

You could use a sieve to generate all primes up to n and then just remove those values from the input vector, as also suggested above. This may be quicker and easier to understand, especially if you store the primes somewhere.

If you're going to test each number individually (using, I guess, and inverse sieve) then I suggest testing each number individually, in order. IMHO it'll be easier to understand than the way you've written it - testing each number for divisibility by k < n for ever increasing k.

Answer 7

Your code seems to have many problems:

1. If you want to test if your number is prime or non-prime, you would need to check for v[j] % i == 0, not the other way round
2. You did not check if your number is dividing by itself
3. You keep on checking your numbers again and again. That's very inefficient.

As other guys suggested, you need to do something like the Sieve of Eratosthenes.

So a pseudo C code for your problem would be (I haven't run this through compilers yet, so please ignore syntax errors. This code is to illustrate the algorithm only)

vector<int> inputNumbers;

// First, find all the prime numbers from 1 to n
bool isPrime[n+1] = {true};
isPrime[0]= false;
isPrime[1]= false;
for (int i = 2; i <= sqrt(n); i++)
{
  if (!isPrime[i])
    continue;
  for (int j = 2; j <= n/i; j++)
    isPrime[i*j] = false;
}

// Check the input array for non-prime numbers
for (int i = 0; i < inputNumbers.size(); i++)
{
   int thisNumber = inputNumbers[i];
   // Vet the input to make sure we won't blow our isPrime array
   if ((0<= thisNumber) && (thisNumber <=n))
   {
      // Prints out non-prime numbers
      if (!isPrime[thisNumber])
         cout<< thisNumber;
   }
}

Answer 8

sorting the number first might be a good start - you can do that in nLogN time. That is a small addition (I think) to your other problem - that of finding if a number is prime.
(actually, with a small set of numbers like that you can do a sort much faster with a copy of the size of the vector/set and do a hash/bucket sort/whatever)

I'd then find the highest number in the set (I assume the numbers can be unbounded - no know upper limit until your sort - or do a single pass to find the max)

then go with a sieve - as others have said

Answer 9

Jeremy is right, the basic problem is your i % v[j] instead of v[j] % i.

Try this:

void sieve(vector<int> v, int n) {
  int i,j;

  for(j = 0; j <= n; j++) {
    cout << v[j] << ": ";

    for(i = 2; i < v[j]; i++) {
      if(v[j] % i == 0) {
        cout << "is divisible by " << i << endl;
        break;
      }
    }

    if (i == v[j]) {
      cout << "is prime." << endl;
    }
  }
}

It's not optimal, because it's attempting to divide by all numbers less than v[j] instead of just up to the square root of v[j]. And it is attempting dividion by all numbers instead of only primes.

But it will work.