il forum ufficiale delle olimpiadi della matematica
https://www.oliforum.it/
doh! mi hai sgamato...trugruo ha scritto:rsa
questo problema era diciamo ironico, ma che potrebbe portare qualcuno ad avere idee interessanti sulla fattorizzazione dei numeri, questione molto importante per la matematica.xXStephXx ha scritto:Non capisco dove sta la matematicità in questo problema.. Bisogna trovare il metodo per trovare i numeri a mano?
Ci ho messo un secondo a numero...giro94 ha scritto: forse con questi n di 8 cifre ce la si può fare lo stesso, ma è una rottura...
in che modo hai fatto?Drago96 ha scritto:Ci ho messo un secondo a numero...giro94 ha scritto: forse con questi n di 8 cifre ce la si può fare lo stesso, ma è una rottura...
Comunque quale sarebbe la tua idea??
Programma...giro94 ha scritto:in che modo hai fatto?Drago96 ha scritto:Ci ho messo un secondo a numero...giro94 ha scritto: forse con questi n di 8 cifre ce la si può fare lo stesso, ma è una rottura...
Comunque quale sarebbe la tua idea??
(il mio computer si impalla se do al mio programmino numeri simili... 
)Ehm... potresti fare un esempio??giro94 ha scritto:io pensavo di partire dal test di disibilità generale, imponendo che sia corretto..
cioè provo a vedere se n è divisibile per p, e impongo che lo sia, così posso ricavare p da n.. il problema è che c'è un "mod p" che non mi convince, ho utilizzato fermat per toglierlo, ma poi non funziona..
Ci credo, è javascript! E il tuo isInteger è scritto penso nel modo più lento che potevi trovare XD (return s==Math.round(s) ?)Drago96 ha scritto: Programma...Testo nascosto:
)
Codice: Seleziona tutto
#include <iostream>
#include <gmp.h>
using namespace std;
void smallestfactor(mpz_t n,mpz_t* p,mpz_t* f){
if (mpz_probab_prime_p(n,mpz_sizeinbase(n,4)+10)){
mpz_set(*f,n);
return;
}
if(mpz_divisible_ui_p(n,2)){
mpz_set_ui(*f,2);
return;
}
if(mpz_divisible_ui_p(n,3)){
mpz_set_ui(*f,3);
return;
}
if(mpz_divisible_ui_p(n,5)){
mpz_set_ui(*f,5);
return;
}
mpz_t a;
mpz_init(a);
mpz_sqrt(a,n);
for(;mpz_cmp(*p,a)<=0;mpz_add_ui(*p,*p,6)){
if(mpz_divisible_p(n,*p)){
mpz_set(*f,*p);
return;
}
mpz_add_ui(*p,*p,4);
if(mpz_divisible_p(n,*p)){
mpz_set(*f,*p);
mpz_sub_ui(*p,*p,4);
return;
}
mpz_add_ui(*p,*p,2);
if(mpz_divisible_p(n,*p)){
mpz_set(*f,*p);
mpz_sub_ui(*p,*p,6);
return;
}
mpz_add_ui(*p,*p,4);
if(mpz_divisible_p(n,*p)){
mpz_set(*f,*p);
mpz_sub_ui(*p,*p,10);
return;
}
mpz_add_ui(*p,*p,2);
if(mpz_divisible_p(n,*p)){
mpz_set(*f,*p);
mpz_sub_ui(*p,*p,12);
return;
}
mpz_add_ui(*p,*p,4);
if(mpz_divisible_p(n,*p)){
mpz_set(*f,*p);
mpz_sub_ui(*p,*p,16);
return;
}
mpz_add_ui(*p,*p,6);
if(mpz_divisible_p(n,*p)){
mpz_set(*f,*p);
mpz_sub_ui(*p,*p,22);
return;
}
mpz_add_ui(*p,*p,2);
if(mpz_divisible_p(n,*p)){
mpz_set(*f,*p);
mpz_sub_ui(*p,*p,24);
return;
}
}
cout<<"Qualcosa non va!";
return;
}
int main(){
char *nm;
nm=new char[100000000];
mpz_t n;
mpz_t t;
mpz_t p;
cout<<"Inserisci il numero da fattorizzare: ";
cin>>nm;
mpz_init_set_str(n,nm,10);
mpz_init(t);
mpz_init_set_ui(p,7);
while(mpz_cmp_ui(n,1)){
smallestfactor(n,&p,&t);
mpz_divexact(n,n,t);
cout<<t<<" "<<flush;
}
return 0;
}