Sorting prime function in ascending order

[darkknight914]

I created the void AllPrimes function to display all the primes numbers. However, I need it to display the Prime numbers in ascending order. Right now it displays them in descending order.

 void AllPrimes (size_t n, std::ostream& os = std::cout, bool ticker = 0) {
    if (n >= n+1)          
    {
      std::cerr << " ** Prime: argument too large for implementation. Execution terminating.\n";
      exit (EXIT_FAILURE);
    }
    if (n <= 1) {
        return;
    }

    data::BVector b(1+n); 
    Sieve(b, ticker);

    if (n%2 == 0) --n;     // make n odd
    while (n > 2)          
    {
      if (b[n]) {
        os << b[n] << " ";
      }
      n -= 2;
    }
    os << endl;
}

[salem c]

So make your while loop count up, rather than down.

[darkknight914]

How would I do that? I tried to make n +=2; but that will only give me 2

[marko312]

If you need all primes, note that this code omits the prime 2.

[darkknight914]

The last line should be os << "2\n";

That's how I get my 2. I'm supposed to mimic this function:

size_t PrimeBelow (size_t n, bool ticker)
  // returns largest prime number <= n
  {
    if (n <= 1) return 0;
    if (n == 2) return 2;
    if (n >= n+1)          
    {
      std::cerr << " ** PrimeBelow: argument too large for implementation. Execution terminating.\n";
      exit (EXIT_FAILURE);
    }
    fsu::BitVector b(1+n); 
    Sieve(b, ticker);
    if (n%2 == 0) --n;     // make n odd
    while (n > 2)          
    {
      if (b[n])
        return n;
      n -= 2;
    }
    return 2;
  } 

[E0p9LyTq]

I need it to display the Prime numbers in ascending order. Right now it displays them in descending order.

A crude change you could make is:

1. create a temporary, empty std::vector at the start of your function

2. store each prime in a std:vector as it is created instead of printing it out.

3. use std::sort from <algorithm> to get the primes in ascending order

4. modify your return type to std::vector, remove the std::ostream& parameter and at the end of your function return the temp std::vector.

5. print out your now ascending primes in your caller. :)

[darkknight914]

I'm not allowed to use <algorithm>

[salem c]

It's odd that you've done so much, yet can't get

size_t c = 0;
while ( c <= n ) {
  if (b[c]) {
    os << b[c] << " ";
  }
  c += 2;
}

[marko312]

salem, that would miss almost every prime.

[darkknight914]

I'm still having trouble with this. After implementing

size_t c = 0;
while ( c <= n ) {
  if (b[c]) {
    os << b[c] << " ";
  }
  c += 2;
}

I now end up with even numbers. For instance, when I use 12 I get 2, 4, 6, 8, 10.

[E0p9LyTq]

I'm not allowed to use <algorithm>

Since your code creates primes in descending order, if you can use a std::vector as storage there is no need to sort the container. Simply start the output at the end of the vector and reverse loop through the elements.

[salem c]

> I now end up with even numbers.
Gee, start at 1 then if you want all the odd numbers.

[lastchance]

If b[c] evaluates to true for any even value of c other than 2 then there's something wrong with your Sieve() routine.