semplice fattorizzazione

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
giro94
Messaggi: 171
Iscritto il: 12 nov 2009, 22:11
Località: riccione
Contatta:

semplice fattorizzazione

Messaggio da giro94 » 09 lug 2011, 23:23

ecco un esercizietto semplice semplice..

preso un intero n abbastanza grande, tale che n=p*q dove p e q sono numeri primi, determinare p e q.

lista di n:
-35129987
-19755661
-53549227

good luck! :D
----->[url=http://rubik.forumcommunity.net/]RUBIK'S COMMUNITY![/url]<-----
---->[url=http://varietytribe.forumcommunity.net/]http://varietytribe.forumcommunity.net/[/url]<----
-->[url=http://www.youtube.com/user/giro9414]canale di youtube![/url]<--

xXStephXx
Messaggi: 471
Iscritto il: 22 giu 2011, 21:51

Re: semplice fattorizzazione

Messaggio da xXStephXx » 09 lug 2011, 23:52

Scusa la domanda: posso fattorizzare con qualunque mezzo o non posso usare calcolatori?

giro94
Messaggi: 171
Iscritto il: 12 nov 2009, 22:11
Località: riccione
Contatta:

Re: semplice fattorizzazione

Messaggio da giro94 » 10 lug 2011, 10:06

possibilmente senza calcolatori automatici (esempio programmi al computer)
----->[url=http://rubik.forumcommunity.net/]RUBIK'S COMMUNITY![/url]<-----
---->[url=http://varietytribe.forumcommunity.net/]http://varietytribe.forumcommunity.net/[/url]<----
-->[url=http://www.youtube.com/user/giro9414]canale di youtube![/url]<--

Blue Sky_1993
Messaggi: 17
Iscritto il: 30 giu 2011, 15:15
Località: Terni

Messaggio da Blue Sky_1993 » 10 lug 2011, 11:35

.
Ultima modifica di Blue Sky_1993 il 17 feb 2012, 12:12, modificato 3 volte in totale.

trugruo
Messaggi: 192
Iscritto il: 31 ago 2009, 15:04

Re: semplice fattorizzazione

Messaggio da trugruo » 10 lug 2011, 11:58

rsa

giro94
Messaggi: 171
Iscritto il: 12 nov 2009, 22:11
Località: riccione
Contatta:

Re: semplice fattorizzazione

Messaggio da giro94 » 10 lug 2011, 12:06

trugruo ha scritto:rsa
doh! mi hai sgamato...

beh la fattorizzazione di numeri grandi è uno dei più grandi problemi del momento...
se ti do un numero di 160 cifre, ci metti anni a trovare i suoi divisori col metodo che hai detto te, blue_sky...

forse con questi n di 8 cifre ce la si può fare lo stesso, ma è una rottura...

io avevo in mente un modo nuovo, che però ancora non funziona perfettamente...
----->[url=http://rubik.forumcommunity.net/]RUBIK'S COMMUNITY![/url]<-----
---->[url=http://varietytribe.forumcommunity.net/]http://varietytribe.forumcommunity.net/[/url]<----
-->[url=http://www.youtube.com/user/giro9414]canale di youtube![/url]<--

Blue Sky_1993
Messaggi: 17
Iscritto il: 30 giu 2011, 15:15
Località: Terni

Messaggio da Blue Sky_1993 » 10 lug 2011, 13:22

.
Ultima modifica di Blue Sky_1993 il 17 feb 2012, 12:12, modificato 1 volta in totale.

xXStephXx
Messaggi: 471
Iscritto il: 22 giu 2011, 21:51

Re: semplice fattorizzazione

Messaggio da xXStephXx » 10 lug 2011, 15:24

Non capisco dove sta la matematicità in questo problema.. Bisogna trovare il metodo per trovare i numeri a mano?

giro94
Messaggi: 171
Iscritto il: 12 nov 2009, 22:11
Località: riccione
Contatta:

Re: semplice fattorizzazione

Messaggio da giro94 » 10 lug 2011, 20:20

non lo so, secondo me è risolvibile, ma data la complessità della cosa non assicuro niente..
xXStephXx ha scritto:Non capisco dove sta la matematicità in questo problema.. Bisogna trovare il metodo per trovare i numeri a mano?
questo problema era diciamo ironico, ma che potrebbe portare qualcuno ad avere idee interessanti sulla fattorizzazione dei numeri, questione molto importante per la matematica.
----->[url=http://rubik.forumcommunity.net/]RUBIK'S COMMUNITY![/url]<-----
---->[url=http://varietytribe.forumcommunity.net/]http://varietytribe.forumcommunity.net/[/url]<----
-->[url=http://www.youtube.com/user/giro9414]canale di youtube![/url]<--

Avatar utente
Drago96
Messaggi: 1142
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: semplice fattorizzazione

Messaggio da Drago96 » 11 lug 2011, 10:17

giro94 ha scritto: forse con questi n di 8 cifre ce la si può fare lo stesso, ma è una rottura...
Ci ho messo un secondo a numero...

Comunque quale sarebbe la tua idea??
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

giro94
Messaggi: 171
Iscritto il: 12 nov 2009, 22:11
Località: riccione
Contatta:

Re: semplice fattorizzazione

Messaggio da giro94 » 11 lug 2011, 11:48

Drago96 ha scritto:
giro94 ha scritto: forse con questi n di 8 cifre ce la si può fare lo stesso, ma è una rottura...
Ci ho messo un secondo a numero...

Comunque quale sarebbe la tua idea??
in che modo hai fatto?

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..
----->[url=http://rubik.forumcommunity.net/]RUBIK'S COMMUNITY![/url]<-----
---->[url=http://varietytribe.forumcommunity.net/]http://varietytribe.forumcommunity.net/[/url]<----
-->[url=http://www.youtube.com/user/giro9414]canale di youtube![/url]<--

xXStephXx
Messaggi: 471
Iscritto il: 22 giu 2011, 21:51

Re: semplice fattorizzazione

Messaggio da xXStephXx » 11 lug 2011, 12:02

Credo con un programma :lol: :lol:

Avatar utente
Drago96
Messaggi: 1142
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: semplice fattorizzazione

Messaggio da Drago96 » 11 lug 2011, 12:23

giro94 ha scritto:
Drago96 ha scritto:
giro94 ha scritto: forse con questi n di 8 cifre ce la si può fare lo stesso, ma è una rottura...
Ci ho messo un secondo a numero...

Comunque quale sarebbe la tua idea??
in che modo hai fatto?
Programma... :)
Testo nascosto:

Codice: Seleziona tutto

<script type="text/javascript">
function isInteger(s) {
  return (s.toString().search(/^-?[0-9]+$/) == 0);
}
function div_primi(num) {
n=parseInt(num);
rad1=Math.sqrt(n);
rad=Math.round(rad1);
for (i=2;i<=rad;i++) {
prova=n/i;
if (isInteger(prova)) {
div1=prova;
div2=i;
break;
};
}
document.write(div1+" "+div2);
}
</script>
Sennò usiamo WolframAlpha! 5 secondi per 50 cifre! :o (il mio computer si impalla se do al mio programmino numeri simili... :( )
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..
Ehm... potresti fare un esempio?? :roll:
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

Veluca
Messaggi: 185
Iscritto il: 27 dic 2008, 01:08
Località: Chiavari (Genova)

Re: semplice fattorizzazione

Messaggio da Veluca » 14 lug 2011, 23:07

Drago96 ha scritto: Programma... :)
Testo nascosto:

Codice: Seleziona tutto

<script type="text/javascript">
function isInteger(s) {
  return (s.toString().search(/^-?[0-9]+$/) == 0);
}
function div_primi(num) {
n=parseInt(num);
rad1=Math.sqrt(n);
rad=Math.round(rad1);
for (i=2;i<=rad;i++) {
prova=n/i;
if (isInteger(prova)) {
div1=prova;
div2=i;
break;
};
}
document.write(div1+" "+div2);
}
</script>
Ci credo, è javascript! E il tuo isInteger è scritto penso nel modo più lento che potevi trovare XD (return s==Math.round(s) ?)
EDIT: pro memoria, javascript ha "built-in" i moduli: puoi anche fare n%i==0 invece di prova=n/i isinteger(prova)
(tra un po' ti posto lo stesso programma in C++, pronto a scommettere che a 50 cifre ci arriva senza problemi :D)

Veluca
Messaggi: 185
Iscritto il: 27 dic 2008, 01:08
Località: Chiavari (Genova)

Re: semplice fattorizzazione

Messaggio da Veluca » 15 lug 2011, 15:33

Beh, pensavo di farlo molto più semplice, ma poi mi son lasciato trascinare :D

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;
}

Rispondi