Removing non-prime numbers from a vector

Question

I have a simple function that "primes a list" i.e. it returns the passed vector but without all non-primes. Essentially it removes non-primes from the vector and returns the updated vector. But my function just returns the vector without the numbers 0 and 1. Assume the vector is sorted in ascending order(0, 1, 2, 3, ... ) The basic structure of my function follows:

#include<vector>
#include<algorithms>
#include "cmath.h"
.
.
.
std::vector<int> prime_list(std::vector<int> foo){
   int limit_counter = 1;
   const int p_limit = sqrt(foo.at(foo.size() - 1));

   for(int w = 0; w < foo.size(); w++){
      if(foo.at(w) <= 1)
         foo.erase(foo.begin() + w);
   }

   for(int i : foo){
      do{
         if(i % limit_counter == 0)
            foo.erase(std::remove(foo.begin(), foo.end(), i), foo.end());
         limit_counter++;
      }
      while(limit_counter < p_limit);
   }
   return foo;
}

First thought: are you sure you want to be copying your vector around, or do you want to pass it by reference? `std::vector& prime_list(std::vector& foo)` — Chris, Oct 26 '21 at 00:35
Second thought: You probably want `remove_if` instead of mutating `foo` while you're iterating over it. — Nathan Pierson, Oct 26 '21 at 00:36
@NathanPierson Must I use `remove_if` ? Can I use `remove` Also besides that is there anything wrong with my logic? — LoopGod, Oct 26 '21 at 00:51
Erasing while iterating is trickier to get right than it looks. [Here's a question about a frequent problem that happens to intersect with your code.](https://stackoverflow.com/questions/10360461/removing-item-from-vector-while-in-c11-range-for-loop) — user4581301, Oct 26 '21 at 00:59
And when you used your debugger to run your program one line at a time, and watch the values of all variables, as they change, and see ***exactly*** what the program does, what did you see? — Sam Varshavchik, Oct 26 '21 at 01:10
`for (int i : foo)` where `foo` is modified in the loop body (the statement with `foo.erase()`) causes undefined behaviour. A range-based for loop works with the assumption that iterators (e.g. begin and end of the container `foo`) are not invalidated by the loop body. `foo.erase()` (potentially) invalidates iterators of `foo`. — Peter, Oct 26 '21 at 01:16
`foo.erase(std::remove_if(foo.begin(), foo.end(), [](int n){ return !is_prime(n);}), foo.end());` would do the job (You just have to write `is_prime`). — Jarod42, Oct 26 '21 at 07:58

Barmak Shemirani · Accepted Answer · 2021-10-26T02:30:59.150

const int p_limit = sqrt(foo.at(foo.size() - 1));

This will initialize the limit once, based on the last element in the list. You have to do that for each element being test for prime.

More importantly, limit_counter should be initialized for each i

Ignoring the problem with iterators, you can fix it with this pseudo code.

std::vector<int> prime_list(std::vector<int> foo) 
{
    foo.erase(std::remove(foo.begin(), foo.end(), 0), foo.end());
    foo.erase(std::remove(foo.begin(), foo.end(), 1), foo.end());
    for (int i : foo) 
    {
        int limit_counter = 1;
        const int p_limit = static_cast<int>(sqrt(i));
        do 
        {
            if (i % limit_counter == 0)
            {
                //undefined behavior, this might destroy the iterator for `i`
                foo.erase(std::remove(foo.begin(), foo.end(), i), foo.end());
            }
            limit_counter++;
        } while (limit_counter < p_limit);
    }
    return foo;
}

For an easier and safer solution, just create a new list and add the primes to it. Or, create a duplicate list primes and go through the loop in foo

std::vector<int> prime_list(std::vector<int> &foo) 
{
    std::vector<int> primes = foo;
    primes.erase(std::remove(primes.begin(), primes.end(), 0), primes.end());
    primes.erase(std::remove(primes.begin(), primes.end(), 1), primes.end());
    for (int n : foo)
        for (int k = 2, limit = static_cast<int>(sqrt(n)); k <= limit; k++)
            if (n % k == 0)
                primes.erase(std::remove(primes.begin(), primes.end(), n), primes.end());
    return primes;
}

score 0 · Answer 2 · answered Oct 26 '21 at 11:09

There are basically 2 possible solutions.

You can either erase none prime values from the std::vector
or copy just prime values to a new std::vector

For both solutions it is necessary to have a function, which detects, if a number is a prime or not. There are tons of such functions in the internet. Please select the best for your requirements.

Then, you need to think, if the erase/remove_if or the copy_if solution is better for you.

With erase/remove_if you are shifting a lot of memory, so, if you use it, then maybe better to start from the end.

On the other hand, copy_if may also invoke memory reallocation and copying, because of push_back and back_inserter actions.

So, sorry to say, it depends . . .

Please see below an example with both solutions.

#include <iostream>
#include <vector>
#include <algorithm>

// Some of the many isPrime functions, available in the internet
// Basically, for this example, it does not matter which
bool isPrime(int number){

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

// Version with erase/remove idiom
// Yes, no reference for input parameter. Data shall be copied
auto primeVector1(std::vector<int> data) {
    
    // Remove all none primes
    data.erase(std::remove_if(data.begin(), data.end(), [](const int i){ return not isPrime(i);}),data.end());
 
    return data;
}

// Version with copying prime data to new vector
auto primeVector2(std::vector<int>& data) {
    
    std::vector<int> result{};
    
    // Copy primes to new vector
    std::copy_if(data.begin(), data.end(), std::back_inserter(result), [](const int i){ return isPrime(i);});
 
    return result;
}

// Test/Driver code
int main() {
    std::vector test{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23};
    
    for (const int i : primeVector1(test)) std::cout << i << ' '; std::cout << '\n';
    for (const int i : primeVector2(test)) std::cout << i << ' '; std::cout << '\n';
}

Removing non-prime numbers from a vector

2 Answers2