Static vs. Dynamic Arrays, Getting Undefined Behavior

Hello everyone! First post, and pretty new to C++, so I apologize for any blatantly dumb questions that I may ask. Just trying to learn!

I'm working on a Project Euler problem that has me looking for the largest prime factor of a number. (Specifically, a very large number.) My main programming background is in MATLAB, and I have 3 different versions of code to solve the problem there, but MATLAB is just incapable of handling the value I am trying to evaluate. (~600 billion.) Hence, here's me, trying to learn C++, hoping that it will be efficient enough to handle the problem set forth, as well as furthering my goal of learning C++! hahaha :)

My question is regarding static vs. dynamic memory allocation for arrays. My code is running as expected, but before it was, I was getting some strange errors, and it brought up something I was confused about. At this point, I'm shying away from dynamic arrays just because they seem to be a hair too complicated for my noobishness. I'm trying to get my foundation set in C++ first, then I'll start to tackle some more of the finer points of the language.

In my code, I declare an array "factors" with "halfVal" cells. "halfVal" is defined beforehand, and I don't need it to change later on, so static should be fine, but I'm not sure how to declare it statically by using the value of halfVal. Is it possible to use the value of a variable, in this case halfVal, to statically define the number of cells in an array? If so, how would I do that?

Code:

---

#include <iostream>
#include <cmath>


using namespace std;


int main (int argc, const char * argv[])
{
   
    //Declare variables. Initialization may or may not be necessary?
    int halfVal = 1, counter = 0;
   
    double value = 0, quotient = 0;
   
    //Decalre value to find the largest prime value of
    value = 30; //Goal Value is 600851475143
   
    //Calculate halfVal for efficiency of following for loop
    halfVal = (value / 2) + 1;


    //Declare array. Can I make this a static array while still using the value of halfVal somehow? I don't need a dynamic allocation of memory.
    int factors[halfVal];
   
    //Determine the quotient of the value divided by num (from 2 to halfVal) for logical test
    for( int num = 2; num < halfVal ; num++ ){
       
        quotient = (value / num);
       
       
        //Logical test to determine whether or not num is a factor. If so, store in factors array and update counter
        if( quotient == ceil( quotient ) ) {

            factors [counter] = num;

            counter = counter + 1;
        }
    }
   
    for( int i = 0; i < counter; i++ ) {
        //If counter is replaced with halfVal, then I get undefined behavior. Something to do with dynamic array?
       
        cout << "Factor: " << factors[i] <<"\n";
    }
}

---

Also, another question I have is if I try to access a value in the factors array that is declared, but not redefined in the first for-if loop, then I get undefined behavior when I try to print those values. For example, the factors of 30 are 1, 2, 3, 5, 6, 10, 15, 30. That is 8 total values. If halfVal is set to 16, (and therefore the declaration of the factors array should be 16 total cells) and then I try to print factors[0] through factors[15], after I pass the first 8 cells that have been redefined in the first for-if loop, I get undefined behavior. My output gives me something like:

Factors: 2
Factors: 3
Factors: 5
Factors: 6
Factors: 10
Factors: 15
Factors: 1510532867
Factors: 5937525205
etc.
etc.

(The last several values are obviously the undefined behavior.)

My hunch is that since I have a dynamically allocated array, the values aren't initially defined, so when I try to access them, I get undefined behavior. Is it possible to initialize those values when the array is declared to avoid this type of problem (still keeping it a dynamic array)? If so, how does one go about that. If not, any tips on where I can start to look for a function to clear out the unused cells? No explanation needed, just a point in the right direction for that one. :) I think figuring this out will help me in starting to understand dynamic allocation more. Any insight on this issue would be wonderful!

Thanks so much, and sorry for the long post!

As factors is an automatic variable (on stack), it's not reset and contains garbage when you declare it. It does contains halfVal items (the size is correct). If you add an output in your program when you assign factors[counter], you'll see you only setup the first 6 items (from 0 to 5) so everything else is just random values.

factors is a variable length array, which is a non-standard language feature. You could either create a fixed size array that is as large as you will ever need, or use a container like std::vector:

Code:

---

std::vector<int> factors(halfVal);

---

This should also zero initialise the elements of factors.

Quote:

---

Originally Posted by root4

As factors is an automatic variable (on stack), it's not reset and contains garbage when you declare it. It does contains halfVal items (the size is correct). If you add an output in your program when you assign factors[counter], you'll see you only setup the first 6 items (from 0 to 5) so everything else is just random values.

---

So if I understand correctly, when a variable length array is declared, the initialized "values" of the array are just garbage until I reassign them with something useful. Is that correct?

Quote:

---

Originally Posted by laserlight

factors is a variable length array, which is a non-standard language feature. You could either create a fixed size array that is as large as you will ever need, or use a container like std::vector:

Code:

---

std::vector<int> factors(halfVal);

---

This should also zero initialise the elements of factors.

---

I haven't worked with containers like the one mentioned before, so I am unsure how. Any tutorials you could direct me towards so I can start learning them? The standard vs. non-standard language features concept is still a confusing one for me.

Quote:

---

Originally Posted by StefPrez

So if I understand correctly, when a variable length array is declared, the initialized "values" of the array are just garbage until I reassign them with something useful. Is that correct?

---

You should check your compiler's documentation, but yes :)

Quote:

---

Originally Posted by StefPrez

I haven't worked with containers like the one mentioned before, so I am unsure how. Any tutorials you could direct me towards so I can start learning them?

---

Borrow Josuttis' The C++ Standard Library - A Tutorial and Reference from your local library. It is slightly outdated but still useful.

Quote:

---

For example, the factors of 30 are 1, 2, 3, 5, 6, 10, 15, 30.

---

Euler problem 3 is about prime factors, otherwise finding the largest divisor would be a bit too trivial. The problem might look intimidating, but I suppose it can be solved with simple trial division. You definitely don't need an array that large, and whatever programming language, the memory usage would be too large.

(Tried at ideone.com, Python with trial division by odd integers yields the answer in 0.03 seconds without any array. It only comes down to getting the algorithm right.)

Quote:

---

Originally Posted by anon

Euler problem 3 is about prime factors, otherwise finding the largest divisor would be a bit too trivial. The problem might look intimidating, but I suppose it can be solved with simple trial division. You definitely don't need an array that large, and whatever programming language, the memory usage would be too large.

(Tried at ideone.com, Python with trial division by odd integers yields the answer in 0.03 seconds without any array. It only comes down to getting the algorithm right.)

---

When I finished this problem on the Project Euler site, a PDF became available describing the best way to tackle this problem. There are a few constraints you can place on the loops which drastically cut down computation time.

I won't give you the answer, but links to good methods should come up if you just google "testing for primeness" "finding prime factors"

Edit: I posted as a reply to this post because there IS an element of trial division, but you can do it in a clever way which cuts down on iterations. Also, I don't think I used an array (I don't have the files on this comp). To the OP, if you like math, and I assume you do since you're doing PE problems, there are a few properties of prime and composite numbers that help you out. There are fancy sounding names for the theorems or methods, but it's something you could likely come up with on your own in the pencil and paper realm, by messing around with some (not complicated) algebra.

Quote:

---

Originally Posted by anon

Euler problem 3 is about prime factors, otherwise finding the largest divisor would be a bit too trivial.

---

I know, I said that in the beginning of my post. I was merely just determining factors first, then sorting prime factors from that list. I don't doubt there is a more efficient way to do it, however with C++ still being very new to me, I decided to go with the "easy approach" and then trim the fat or rework the code for efficiency.

Quote:

---

Originally Posted by Ocifer

When I finished this problem on the Project Euler site, a PDF became available describing the best way to tackle this problem. There are a few constraints you can place on the loops which drastically cut down computation time.

I won't give you the answer, but links to good methods should come up if you just google "testing for primeness" "finding prime factors"

Edit: I posted as a reply to this post because there IS an element of trial division, but you can do it in a clever way which cuts down on iterations. Also, I don't think I used an array (I don't have the files on this comp). To the OP, if you like math, and I assume you do since you're doing PE problems, there are a few properties of prime and composite numbers that help you out. There are fancy sounding names for the theorems or methods, but it's something you could likely come up with on your own in the pencil and paper realm, by messing around with some (not complicated) algebra.

---

Thanks! I started to optimize slightly in my MATLAB prototypes, however in MATLAB, the factor function returns prime factors of a number, yet the value used in PE was too large for it. (Max value is 2^32.) At that point, I was pretty confident I had to do it in another language, and C++ was my choice. I will optimize soon, as soon as I have a properly functions version.

I'm not sure this is a matter of optimization, but rather using a rather unsuitable algorithm to begin with. 300 billion trial divisions is way too much work, even if you sort out the memory problems (the large value in question has just a few prime factors, and hence rather few divisors). You could cut it down a little by taking into account that the largest prime factor of composite n can't be larger than sqrt(n).

I would also doubt the floating point math. C++11 has 64-bit integers that is enough for this problem.

But if you insist on finding the divisors, you can add them to a std::vector, which is a dynamically growing array. The reason is that you don't know how many divisors there's going to be (you'd know that after finding how many prime factors there are :) ), could be 10, could be 1000, could be a million.

Yes I'm sorry. I wasn't sure if I would ruin the learning process, but data overflow is one of the intended stumbling blocks of this problem. However, I would be shocked to learn that MATLAB doesn't support long integers (I don't have experience). You should be able to accommodate larger integers in MATLAB, it's serious software. Look for datatype documentation before you change languages just to solve this problem...though I do like c++ :)

Also, consider your own mental processes when you try to factorize smaller (more humane :) ) numbers.

Consider 700

What's the first prime? 2.

2 divides 700 leaving a quotient of 350
2 divides 350 leaving a quotient of 175

2 DOES NOT divide 175

What's the next prime? 3

3 DOES NOT divide 175

What's the next prime? 5

5 divides 175 leaving a quotient of 35
5 divides 35 leaving a quotient of 7

5 doesn't divide 7

next prime: 7

7/7 = 1 and you are done

-----------------------------------

700 = 2^2 * 5^2 * 7

---------------------------------

The way I presented is highly suggestive of how one might program a machine to do it, as a hint. Most people would divide out the 7 first and the 100 falls apart into 25 * 4 = 5^2 * 2^2, but you don't want to complicate this by trying to program intuition. Note I'm not considering even numbers after 2 -- the reason why is not too hard to see.

There are further tweaks which can be done to this basic idea, but this should give you enough efficiency to solve the problem. To really get the most of this problem, make sure to read the PDF that becomes available.

EDIT: So there is an element of trial division, but we don't implement the division operator per se. We're testing divisibility by n, and this is often done using the modulo operator ( % ). One can conceptualize this as slowly "shaving off" factors only if doing so leaves an integer quotient. Bahh I've said too much.

Thanks for all the input and advice everyone! This problem was definitely a multifaceted learning experience for me. Regardless of how one learns the material, the important part is learning it. I think I learned a lot, even if it may have been down the wrong path, but I also learned a lot by you all guiding me towards the light. Much appreciated, once again! Hopefully I'll be able to help people out in a similar fashion one day. I'm a bit too green for that currently, though. :) Best regards!