Dear StackOverflow community,
I am trying to write code that accepts a "primefactorized" array, each element originally describing their final multiplicational product.
The code I'm trying to write then reads this array and turns it to the exponentiation of prime numbers, each index of the array corresponding to the next prime number, and each element on the index the power to which it must be raised. I believe I have done so, but I cannot for some reason get my IO working. For some reason when I switched the inner for-loops last incrementation part to an "i++" instead of the correct "j++", it would display the loop.
Relevant snippet
// Next stage: Take the array and turn in into the form described earlier
for(unsigned int i = 0; i < sizeof(result); i++)
{
temppower = result[i];
tempcounter = 1; // counter to control the loop.
for(unsigned int j = 0; i < sizeof(result)-1; j++)
{
if(result[j]+1 == temppower)
{
tempcounter++;
result[j+1] = 0;
}
}
result[i] = tempcounter;
}
for(unsigned int i = 0; i < sizeof(result); i++)
{
cout << result[i] << " ";
}
cout << endl;
Full code
#include <iostream>
#include <cmath>
#include <climits>
using namespace std;
#include "fact.h"
/** eartosthenes constructs an up-to-n primes array of length len .
* @param n call-by-value, top value for construction of primes.
* @param &len call-by-reference, the finished size of the array of primes.
* @return int* pointer to the first element of the array of primes.
* Description:
* The eartosthenes method of calculating primes are efficient for relative low primes (up to 10 million or so).
* You can read about the method at http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
* You can use wolfram-alpha https://www.wolframalpha.com/ and run Prime(start)...Prime(end) to get the primes
* between start and end, e.g. Prime(1)...Prime(10) yield {2,3,5,7,11,13,17,19,23,29}.
*/
int * eratosthenes(int n, int & len){
// computes all prime numbers up to n
// returns the prime numbers as an array
// the len parameter will be set to the length of the array
bool *isPrime=new bool [n+1]; // construct [n+1] booleans
len=0;
// initialize every value from 1..n to true.
for(int i=2; i<=n; i++){
isPrime[i]=true;
}
// now we'll start at 2, and for every number of multiplicity 2.
// e.g. 2*{1,2,3,4...n} is then set to false, as they are dividable by 2.
// then we increment to 3, during the same.
for(int i=2; i<=n; i++){
if(isPrime[i]){
len++; // for each such iteration, we increase our desired length.
for(int j=2*i; j<=n; j+=i){
isPrime[j]=false; // set every(n) multiplicity of 2 to false.
}
}
}
// having used erathosthenes formula, we now construct our array.
int *result=new int[len];
// now we need to return the primes-filled array.
for(int i=0, j=2; i<len; i++){
// if it's not a prime, then we spin the value up.
while(!isPrime[j]) j++;
// when the while-loop no longer hold, we'll have the iterations desired prime
// we then set it, and the for-loop will continue to the next.
result[i]=j++;
}
delete [] isPrime; // always delete what you have allocated with new.
// we say these allocation are on the heap or free store (c-syntax)
return result;
}
#include "fact.h"
factrep new_factrep()
{
factrep result;
result = new int[len];
return result;
}
factrep primfact(int n)
{
factrep result;
result = new int[len];
int m; // still to factorize number
int f; // current factor
int index = 0; // index of factrep array
int temppower = 0; // index for the power
int tempcounter = 0; // counter to help the power determine its size
m=n;
f=2;
// 0-initialize the result array
for(unsigned int i = 0; i < sizeof(result); i++)
{
result[i] = 0;
}
// continue until nothing to factorize
while(m != 1){
// while the factor divides m, go on
while(m % f == 0){
if(m!=1)
{
m=m/f;
result[index] = f;
index++;
}
else
{
result[index] = f;
break;
}
}
// increment factor
f++;
}
// Next stage: Take the array and turn in into the form described within
// the exercise handout,
for(unsigned int i = 0; i < sizeof(result); i++)
{
temppower = result[i];
tempcounter = 1; // counter to control the loop.
for(unsigned int j = 0; i < sizeof(result)-1; j++)
{
if(result[j]+1 == temppower)
{
tempcounter++;
result[j+1] = 0;
}
}
result[i] = tempcounter;
}
for(unsigned int i = 0; i < sizeof(result); i++)
{
cout << result[i] << " ";
}
cout << endl;
return result;
}
factrep mult(factrep f1, factrep f2)
{
factrep result;
result = new int[len];
for(int i = 0; i < len; i++)
{
result[i] = f1[i]+f2[i];
}
return result;
}
int getint(factrep f)
{
int result = 0;
// int *temparray = new int[len];
for(int i = 0; i < len; i++)
{
result *= pow(primes[i],f[i]);
}
return result;
}
// these are our global variables
// so in our header we called extern
// which basically tells c++, that we'll define them in another file.
int *primes;
int len;
int main(){
// construct our primes array with maximum integer value
primes=eratosthenes(sqrt(INT_MAX),len);
// len now contains the length of the primes.
// TEST VALUES
// these are our test values.
int n=60;
int m=25;
int l=640;
// first check for non-negative content
if ( n < 0 || m < 0 || l < 0){
cout << "values must be positive (n > 0)" << endl;
return 1;
}
// construct 3 prime-factorized arrays by the values (60,25,640)
factrep fn=primfact(n);
factrep fm=primfact(m);
factrep fl=primfact(l);
// Verify that these are indeed constructed with those values
cout << getint(fn) << " " << getint(fm) << " " << getint(fl) << endl;
// multiply: fn = fn*fm, fm = fl*fl, fl = fn*fm
// 1500 = 60*25, 409600 = 640*640, 614400000 = 1500*409600
fn=mult(fn,fm);
fm=mult(fl,fl);
fl=mult(fn,fm);
// Verify that our functions work as expected by printing out their values now.
cout << getint(fn) << " " << getint(fm) << " " << getint(fl) << endl;
/* Expected output:
60 25 640
1500 409600 614400000
*/
// and again, if we construct something on the heap/free-store we better delete it again
// otherwise we might have a memory-leak on our hands.
delete [] primes;
delete [] fn;
delete [] fm;
delete [] fl;
return 0;
}
Update
The error was pointed out to me: I had put an i variable reference within the inner-most loop instead of the j variable I was using. (facepalm).
In the meantime this realization quickly helped me to solve my original problem which I will paste below in case anyone might run into a similar problem (primes[] is an array of primes, one per element, established outside of the factrep functions)
for(unsigned int i = 0; i < sizeof(result); i++)
{
temppower = primes[i];
tempcounter = 0; // counter to control the loop.
for(unsigned int j = 0; j < sizeof(result); j++)
{
if(result[j] == temppower)
{
tempcounter++;
}
}
result[i] = tempcounter;
}
factrep
seems to be anint*
. Applyingsizeof
to a pointer gives you the size of the pointer (4 or 8, most likely) and not the size of the allocation.