Faktorisierung von Zahlen

karl05

Wie ist es in C++ möglich eine Zahl zu faktorisieren? Gibt es da nicht bestimmte vorgehensweisen oder Befehle die dies vereinfachen? Wäre nett wenn einer ein Codebeispiel oder ein Codeschnipsel zur Verfügung stellen würde.

Vorden

wie is Faktorisieren gemeint, Primfaktorzerlegung?

volkard

karl05 schrieb:

Wie ist es in C++ möglich eine Zahl zu faktorisieren?

ich empfehle, die möglichen teiler durchzuprobieren.

Gibt es da nicht bestimmte vorgehensweisen oder Befehle die dies vereinfachen?

ja.
t ist teiler von z, wenn z%t==0

Wäre nett wenn einer ein Codebeispiel oder ein Codeschnipsel zur Verfügung stellen würde.

vielleicht sowas.

void factor(unsigned int x){
   for(unsigned int t=2;t*t<=x;++t){
      while(x%t==0){
         cout<<t<<' ';
         x/=t;
      }
   }
}

oder in der harten version eher so

template<typename A,typename B>
Pair<A,B> makePair(A const& a,B const& b){
    return Pair<A,B>(a,b);
}

Pair<u64,u64> factorByPollardsRho(u64 n){
    u64 c0=n-1;
    u64 x0=2;
restart:
    u64 x=x0;
    for(u64 i=33;;++i){
        if(!(i&i-1))
            x0=x;
        x=mulModUnguarded(x,x,n);
        x=addModUnguarded(x,c0,n);
        u64 a=(x>x0?x-x0:x0-x);
        if(a==0){
            c0-=2;
            goto restart;
        }
        u64 g=gcd(n,a);
        if(g!=1)
            return makePair(g,n/g);
    }
}

void getPrimeFactorsByPollardsRho(Vector<u64,64>& result,u64 n){
    if(isPrime(n)){
        u64* pos=new(result) u64(n);
        while(pos!=result.getBegin() && *pos<*(pos-1)){
            swap(*pos,*(pos-1));
            --pos;
        }
        return;
    }
    Pair<u64,u64> p=factorByPollardsRho(n);
    getPrimeFactorsByPollardsRho(result,p.a);
    getPrimeFactorsByPollardsRho(result,p.b);
} 

Vector<u64,64> getPrimeFactors(u64 n){
    assert(n>1);
    Vector<u64,64> result;
    while(n%2==0){
        new(result) u64(2);
        n/=2;
    }
    while(n%3==0){
        new(result) u64(3);
        n/=3;
    }
    while(n%5==0){
        new(result) u64(5);
        n/=5;
    }
    while(n%7==0){
        new(result) u64(7);
        n/=7;
    }
    if(n>1)
        getPrimeFactorsByPollardsRho(result,n);
    return result;
}

ähm. ein goto! ich hab ein goto gefunden. *hüpf*

karl05

Danke volkard!

Der Code zum Faktorisieren ist schon gut:

void factor(unsigned int x){
   for(unsigned int t=2;t*t<=x;++t){
      while(x%t==0){
         cout<<t<<' ';
         x/=t;
      }
   }
}

, wenn man z.B. 27 geht es mit diesem Code wunderbar auf. Es kommt nämlich 3, 3, 3 raus. Aber wenn man andere Zahlen benutzt wie z.B. 10 dann zeigt er nur die 2 an.
Wie ändert man denn Code so das er auch die Zahlen anzeigt die größer als 3 sind?
Vielleicht wie Vorden angedeutet hat in Primfaktorzerlegung?

Danke.

volkard

vielleicht

void factor(unsigned int x){
   for(unsigned int t=2;t*t<=x;++t){
      while(x%t==0){
         cout<<t<<' ';
         x/=t;
      }
   }
   cout<<x<<' ';
}

aber ich müßte drüber nachdenken, warum er manchmal noch ne 1 schreibt und manchmal nicht und wie man das wegmacht. aber das ist dein job.

volkard schrieb:

vielleicht
void factor(unsigned int x){
   for(unsigned int t=2;t*t<=x;++t){
      while(x%t==0){
         cout<<t<<' ';
         x/=t;
      }
   }
   cout<<x<<' ';
}
aber ich müßte drüber nachdenken, warum er manchmal noch ne 1 schreibt und manchmal nicht und wie man das wegmacht. aber das ist dein job.

Änder mal

for(unsigned int t=2;t*t<=x;++t){

in

for(unsigned int t=2;t*t<=x;t++){

Dann müsste die 1 weg sein! (Die kann man sich ja konstant dazuschreiben, da sie ja immer auftritt). So verschwindet das "manchmal"

volkard

tghdfgfdg schrieb:

Änder mal
for(unsigned int t=2;t*t<=x;++t){
in
for(unsigned int t=2;t*t<=x;t++){
Dann müsste die 1 weg sein! (Die kann man sich ja konstant dazuschreiben, da sie ja immer auftritt). So verschwindet das "manchmal"

http://www.volkard.de/Cpp/FAQ/Cpp/ppiterator_oder_iteratorpp_bei_for-schleife/index.html

camper

volkard schrieb:

vielleicht
void factor(unsigned int x){
   for(unsigned int t=2;t*t<=x;++t){
      while(x%t==0){
         cout<<t<<' ';
         x/=t;
      }
   }
   cout<<x<<' ';
}
aber ich müßte drüber nachdenken, warum er manchmal noch ne 1 schreibt und manchmal nicht und wie man das wegmacht. aber das ist dein job.

der test t*t<=x müsste nach jeder division erfolgen, und nicht nur, wenn t erhöht wird. andernfalls wird 1 ausgegeben falls die grösste primzahl in x mehrfach vorhanden ist.

void factor(unsigned int x){
   for(unsigned int t=2;t*t<=x;){
      if(x%t==0){
         cout<<t<<' ';
         x/=t;
      }else{
         t+=2;
      }
   }
   cout<<x<<' ';
}

volkard

camper schrieb:

der test t*t<=x müsste nach jeder division erfolgen, und nicht nur, wenn t erhöht wird. andernfalls wird 1 ausgegeben falls die grösste primzahl in x mehrfach vorhanden ist.
void factor(unsigned int x){
   for(unsigned int t=2;t*t<=x;){
      if(x%t==0){
         cout<<t<<' ';
         x/=t;
      }else{
         t+=2;
      }
   }
   cout<<x<<' ';
}

nette analyse und pfiffige lösung.
ich hatte an

void factor(unsigned int x){ 
   for(unsigned int t=2;t*t<=x;++t){ 
      while(x%t==0){ 
         cout<<t<<' '; 
         x/=t; 
      } 
   } 
   if(x!=1)
      cout<<x<<' '; 
}

gedacht, also ich hätte das problem nicht geheilt, sondern nur die symtome kuriert. hätte? habe es so seit jahren gemacht und dieses problem in der schublade "wunderlichkeiten der algorithmenentwicklung" eingeordnet. immer wieder fein, wenn sich durch sowas mein stil wieder ein wenig verbessert. thx.

camper

ups, wir müssen nat. ++t beibehalten, sonst wirds nichts mit ungeraden zahlen

volkard

camper schrieb:

ups, wir müssen nat. ++t beibehalten, sonst wirds nichts mit ungeraden zahlen

klar, aber die 2 wird eh in ner eigenen schleife vorher gemacht, weil durch 2 teilen so sagenhaft billig ist.

volkard schrieb:

camper schrieb:

ups, wir müssen nat. ++t beibehalten, sonst wirds nichts mit ungeraden zahlen

klar, aber die 2 wird eh in ner eigenen schleife vorher gemacht, weil durch 2 teilen so sagenhaft billig ist.

also so?

void factor(unsigned int x){ 

   while((x&1)==0 && x > 3){
		cout<<2<<' ';
		x>>=1;
   }

   for(unsigned int t=3;t*t<=x;){ 
      if(x%t==0){ 
         cout<<t<<' '; 
         x/=t; 
      }else{ 
         t+=2; 
      } 
   } 
   cout<<x<<' '; 
}