Прайм Факторинг, нет IO
Уважаемое сообщество Stackru,
Я пытаюсь написать код, который принимает "первоклассный" массив, каждый элемент которого первоначально описывает свой конечный мультипликативный продукт.
Код, который я пытаюсь написать, затем читает этот массив и превращает его в возведение в степень простых чисел, каждый индекс массива соответствует следующему простому числу, а каждый элемент индекса - степень, до которой он должен быть возведен. Я верю, что сделал это, но по какой-то причине не могу заставить работать свой IO. По какой-то причине, когда я переключил последнюю часть приращения внутренних циклов for на "i++" вместо правильного "j++", он отобразил бы цикл.
Соответствующий фрагмент
// 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;
Полный код
#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;
}
Обновить
Мне было указано на ошибку: я поместил ссылку на переменную i в самый внутренний цикл вместо переменной j, которую я использовал. (Facepalm).
Тем временем эта реализация быстро помогла мне решить мою исходную проблему, которую я вставлю ниже на случай, если кто-то может столкнуться с подобной проблемой (primes [] - это массив простых чисел, по одному на элемент, созданный вне функций factrep)
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;
}
1 ответ
Решение
Строка 116: цикл бесконечен.
for(unsigned int j = 0; i < sizeof(result)-1; j++)
я никогда не изменяю внутренний цикл, где j увеличивается, что препятствует дальнейшему продвижению вашей программы и печати чего-либо.