CODEWITHSUNDEEP
c++class
Heifetz_Fan
Heifetz_Fan

Reputation: 459

C++ class: calling private function in for-loop from public function

Given a range of large numbers

candidates=[6541367000, 6541368000)

find those can be factorized by only 2 prime numbers.

I wrote a C++ class with:

vector<long long>& prime_fac(N)

returning a vector of N's prime numbers, and

void print2PrimeFactoriation(vector<long long>& candidates)

returning only candidate with 2 prime factors.

#include <cmath>
#include <iostream>
#include <vector>
using namespace std;

class primeFactorization {
private:
    //vector<long long> prime_vec;
    long long upper_limit;
    vector<long long> res;

    vector<long long>& prime_fac(long long N) {
        vector<long long> prime_vec;
        if (N < 2) {
            cout << "N=" << N << " cannot be factorized by prime numbers" << endl;
        }
        else {
            upper_limit = (long long)sqrt(N);
            while (N%2 == 0) {
                prime_vec.emplace_back(2);
                N /= 2;
            }
            for (long long prime=3; prime<=upper_limit; prime+=2) {
                while (N%prime == 0) {
                    prime_vec.emplace_back(prime);
                }
            }
            prime_vec.emplace_back(N);
        }
        return prime_vec;
    }

public:
    void print2PrimeFactoriation(vector<long long>& candidates) {
        for (long long candidate : candidates) {
            res = prime_fac(candidate);
            cout << candidate << endl;
            if (res.size() == 2) {
                cout << candidate << " can be factorized by 2 prime numbers (";
                cout << res[0] << ", " << res[1] << ")\n";
            }
        }
    }
};


int main() {
    primeFactorization sol;

    vector<long long> candidates;
    for (long long candidate=6541367001; candidate<6541368000; candidate+=2) {
        candidates.emplace_back(candidate);
    }

    sol.print2PrimeFactoriation(candidates);

    return 0;
}

Strangely, I got error message:

terminate called after throwing an instance of 'std::bad_alloc'                                                                                                                      
  what():  std::bad_alloc                                                                                                                                                            
Aborted

I even tried to reduce input vector candidates to include only 1 element, but the same error still exists.

What is the bug? What shall I do to fix? Also, is it the most efficient way to do prime factorization?

Upvotes: 1

Views: 198

Answers (1)

P.W
P.W

Reputation: 26800

You are returning reference to a local variable prime_vec in the function vector<long long>& prime_fac(long long N). 

vector<long long>& prime_fac(long long N) {
    vector<long long> prime_vec;
    ...
    ... 
    return prime_vec;
}

The lifetime of the local variable prime_vec here is limited to the scope of the function. Trying to use it after the scope is exited leads to undefined behavior.

Compilers like GCC and Clang issue a warning when you do this:

warning: reference to stack memory associated with local variable 'prime_vec' returned [-Wreturn-stack-address]
        return prime_vec;
               ^~~~~~~~~

Upvotes: 1

Related Questions