CODEWITHSUNDEEP
c++algorithm
Eric
Eric

Reputation: 2705

Can't understand why my program throws error

My code is in

#include <iostream>
#include <string>
#include <algorithm>
#include <climits> 
#include <vector>
#include <cmath>

using namespace std;

struct State {
    int v;
    const State *rest;
    void dump() const {
        if(rest) {
            cout << ' ' << v;
            rest->dump();
        } else {
            cout << endl;
        }
    }
    State() : v(0), rest(0) {}
    State(int _v, const State &_rest) : v(_v), rest(&_rest) {}
};

void ss(int *ip, int *end, int target, const State &state) {
    if(target < 0) return; // assuming we don't allow any negatives
    if(ip==end && target==0) {
        state.dump();
        return;
    }
    if(ip==end)
        return;
    { // without the first one
        ss(ip+1, end, target, state);
    }
    { // with the first one
        int first = *ip;
        ss(ip+1, end, target-first, State(first, state));
    }
}

vector<int> get_primes(int N) {
    int size = floor(0.5 * (N - 3)) + 1;

    vector<int> primes;
    primes.push_back(2);
    vector<bool> is_prime(size, true);

    for(long i = 0; i < size; ++i) {
       if(is_prime[i]) {
           int p = (i << 1) + 3;
           primes.push_back(p);
           // sieving from p^2, whose index is 2i^2 + 6i + 3
           for (long j = ((i * i) << 1) + 6 * i + 3; j < size; j += p) {
               is_prime[j] = false;
           }
       }
    }
}

int main() {
    int N;
    cin >> N;
    vector<int> primes = get_primes(N);

    int a[primes.size()];

    for (int i = 0; i < primes.size(); ++i) {
        a[i] = primes[i];
    }

    int * start = &a[0];
    int * end = start + sizeof(a) / sizeof(a[0]);
    ss(start, end, N, State());
}

It takes one input N (int), and gets the vector of all prime numbers smaller than N.

Then, it finds the number of unique sets from the vector that adds up to N.

The get_primes(N) works, but the other one doesn't.

I borrowed the other code from How to find all matching numbers, that sums to 'N' in a given array

Please help me.. I just want the number of unique sets.

Upvotes: 0

Views: 67

Answers (2)

Barry
Barry

Reputation: 303147

I'm guessing the problem is:

vector<int> get_primes(int N) {
    // ...
    return primes; // missing this line
}

As-is, you're just writing some junk here:

vector<int> primes = get_primes(N);

it's undefined behavior - which in this case manifests itself as crashing.

Upvotes: 1

Jonathan Potter
Jonathan Potter

Reputation: 37152

You've forgotten to return primes; at the end of your get_primes() function.

Upvotes: 1

Related Questions