scomposizione in fattori primi
Ignorante
leggero offline (cioè un programma di piccole dimensioni da usare senza
essere collegati a internet) per effettuare la scomposizione di un
numero in fattori primi? Potrebbe andare bene anche Excel o Calc, se mi
dite che esiste una funzione apposita...
Roberto Montaruli
Crivello di Eratostene.
nano bagonghi
Il crivello di Eratostene e' un procedimento che serve per
determinare i numeri primi, non per fattorizzare un numero.
In rete penso tu possa trovare diversi programmi.
A scrivere un programma per scomporre in fattori primi
un numero piccolo (per esempio con max 10 cifre) un
programmatore anche scarso non ci dovrebbe mettere piu'
di 10 minuti.
Per esempio, un programmino siffatto lo trovi in questa
pagina
http://www.didattica.org/matematica.htm
alla voce "scomposizione in fattori primi": per quanto
rudimentale, sembra funzionare.
ciao,
g.
Roberto Montaruli
> Roberto Montaruli wrote:
> > Ignorante ha scritto:
> >
> >> Scusate la mia assoluta ignoranza in materia, conoscete uno strumento
> >> leggero offline (cioč un programma di piccole dimensioni da usare
> >> senza essere collegati a internet) per effettuare la scomposizione di
> >> un numero in fattori primi? Potrebbe andare bene anche Excel o Calc,
> >> se mi dite che esiste una funzione apposita...
> >
> >
> > Crivello di Eratostene.
> Il crivello di Eratostene e' un procedimento che serve per
> determinare i numeri primi, non per fattorizzare un numero.
Certo, ma se non determini i numeri primi, come fai a fattorizzare un
numero intero?
--
questo articolo e` stato inviato via web dal servizio gratuito
http://www.newsland.it/news segnala gli abusi ad ab...@newsland.it
Bruno Campanini
news:47684136$0$36445$4faf...@reader5.news.tin.it...
> Il crivello di Eratostene e' un procedimento che serve per
> determinare i numeri primi, non per fattorizzare un numero.
>
> In rete penso tu possa trovare diversi programmi.
> A scrivere un programma per scomporre in fattori primi
> un numero piccolo (per esempio con max 10 cifre) un
> programmatore anche scarso non ci dovrebbe mettere piu'
> di 10 minuti.
Mi piacerebbe giocarmi le palle, mettendoti al lavoro,
cronometro alla mano...
Bruno
Cristiano
Hai già trovato le forbici adatte? :-)
Non so se sei programmatore, ma è una cosa veramente banale scrivere qualche
riga di programma per il crivello e qualche altra riga aggiuntiva per
trovare i numeri primi che dividono il numero da fattorizzare.
Non è quello che chiedeva l'OP, ma per scrivere un programma che funziona in
una finestra del DOS forse bastano 5 minuti; non voglio fare lo spaccone!
:-)
Cristiano
Cristiano
>> Il crivello di Eratostene e' un procedimento che serve per
>> determinare i numeri primi, non per fattorizzare un numero.
>
> Certo, ma se non determini i numeri primi, come fai a fattorizzare un
> numero intero?
Si potrebbe dire che il crivello non è un algoritmo di fattorizzazione, ma è
molto utile (e veloce) per fattorizzare numeri "piccoli" (fino a 50-55 bit).
Cristiano
Bruno Campanini
news:47691574$0$36448$4faf...@reader5.news.tin.it...
> Hai già trovato le forbici adatte? :-)
> Non so se sei programmatore, ma è una cosa veramente banale scrivere
> qualche riga di programma per il crivello e qualche altra riga aggiuntiva
> per trovare i numeri primi che dividono il numero da fattorizzare.
> Non è quello che chiedeva l'OP, ma per scrivere un programma che funziona
> in una finestra del DOS forse bastano 5 minuti; non voglio fare lo
> spaccone! :-)
>
> Cristiano
Sì, sono programmatore, e per questo sostengo che in 5-10 minuti
si riesce a prendere sì e no un caffè.
Non che ci voglia tanto per il problema di specie, ma su quel tempo
vorrei mettere alla prova te e quell'altro.
D'altro canto, ad evitare il sospetto di spacconeria, mandami
un programmino fatto di "qualche riga di programma per il
crivello e qualche altra aggiuntiva per trovare i numeri primi..."
Che ci vuole? roba di 5-10 minuti!
Bruno
nano bagonghi
> "nano bagonghi" <nano.bag...@CUTgmail.com> wrote in message
>>A scrivere un programma per scomporre in fattori primi
>>un numero piccolo (per esempio con max 10 cifre) un
>>programmatore anche scarso non ci dovrebbe mettere piu'
>>di 10 minuti.
>
> Mi piacerebbe giocarmi le palle, mettendoti al lavoro,
> cronometro alla mano...
Guarda, senza correre particolarmente, ci ho messo meno di 4 minuti.
(Se ti fidi...) Il programma in C e' questo :
#include<stdio.h>
#include<stdlib.h>
int main(int argc, char *argv[])
{
long long int n;
int p;
if (argc!=2 || (n=atoll(argv[1]))<=1) return 0;
while ((n&1)==0) {printf("2 "); n/=2;}
for (p=3; p*p<=n; p+=2)
while (0==(n%p)) {printf("%d ",p); n/=p;}
if (n>1) printf("%lld",n);
printf("\n");
return 0;
}
cioa,
g.
Bruno Campanini
> Guarda, senza correre particolarmente, ci ho messo meno di 4 minuti.
> (Se ti fidi...) Il programma in C e' questo :
>
> #include<stdio.h>
> #include<stdlib.h>
>
> int main(int argc, char *argv[])
> {
> long long int n;
> int p;
> if (argc!=2 || (n=atoll(argv[1]))<=1) return 0;
> while ((n&1)==0) {printf("2 "); n/=2;}
> for (p=3; p*p<=n; p+=2)
> while (0==(n%p)) {printf("%d ",p); n/=p;}
> if (n>1) printf("%lld",n);
> printf("\n");
> return 0;
> }
>
> cioa,
> g.
Averlo fatto e testato con almeno 5-6 numeri di varia
lunghezza dei quali conosci esattamente i fattori in
meno di quattro minuti... o sei un genio o l'avevi già
fatto o sei un bugiardo!
Per me sei un genio.
Bruno
nano bagonghi
> Bruno Campanini wrote:
>
>> "nano bagonghi" <nano.bag...@CUTgmail.com> wrote in message
>>
>>> A scrivere un programma per scomporre in fattori primi
>>> un numero piccolo (per esempio con max 10 cifre) un
>>> programmatore anche scarso non ci dovrebbe mettere piu'
>>> di 10 minuti.
>>
>> Mi piacerebbe giocarmi le palle, mettendoti al lavoro,
>> cronometro alla mano...
>
> Guarda, senza correre particolarmente, ci ho messo meno di 4 minuti.
> (Se ti fidi...) Il programma in C e' questo :
Volevo aggiungere (oltre al mio nome e cognome in calce,
visto che qui ci si giocavano i gioielli di famiglia :-) )
che quello che ho postato funziona a linea di comando,
cioe' uno scrive per esempio
pippo 123456789
e quello stampa i fattori ovvero 3 3 3607 3803
Per fattorizzare i numeri maggiori di 2^31 bisogna aggiungere
un cast nel test del for, cioe' p*(long long) p<=n invece di p*p<=n.
E volevo aggiungere anche che il programmino
funziona, ma e' stato pensato per essere scritto in velocita',
non per essere particolarmente performante.
A programmare un crivello, per quanto sia una cosa piuttosto facile,
ci avrei messo sicuramente di piu'.
Io non sono un programmatore, ma bene o male sono piu'
di 25 (acc!) anni che programmicchio.
ciao,
giovanni "nano bagonghi" resta
http://www.iit.cnr.it/staff/giovanni.resta
nano bagonghi
> Averlo fatto e testato con almeno 5-6 numeri di varia
> lunghezza dei quali conosci esattamente i fattori in
> meno di quattro minuti... o sei un genio o l'avevi già
> fatto o sei un bugiardo!
>
> Per me sei un genio.
Non sono un bugiardo e tanto meno (purtroppo) un genio.
Il programma l'ho testato:
for i in `seq 2 25`; do echo $i `pippone $i`; done
dopo averlo scritto. E non l'ho conteggiato nel
tempo di scrittura, visto che il programma era
gia' corretto.
Sul fatto di averlo gia' fatto altre volte, e' certo.
Mi ricordo che un mio programmino per la mitica
TI-59 (sara' stato il 1979 o il l980) ci mise svariate
ore per verificare che 9*10^9+1 e' primo.
Programmetti di carattere matematico-ludico ne avro' scritti
svariate centinaia.
A volte mi diverto con i problemi su http://www.primepuzzles.net/
In questo caso ci voleva poco tempo perche'
il programma e' una traduzione
pari pari del metodo piu' scemo del mondo che si insegna
alle elementari:
prima dividi ripetutamente per 2 fino a che il numero e' pari,
e poi provi a dividere per i numeri
dispari x fino a che x*x non eccede il numero che
stai fattorizzando.
Se questa cosa l'hai ben chiara in mente, a tradurla
in un programma di 10 righe non ci vuole molto.
Naturalmente se uno deve reinventarsi il metodo
per fattorizzare i numeri ci mette piu' tempo, ma davo
per scontato che qui su it.sciena.matematica
non si partisse da cosi' in basso :-)
ciao,
g.
Roberto Montaruli
> In questo caso ci voleva poco tempo perche'
> il programma e' una traduzione
> pari pari del metodo piu' scemo del mondo che si insegna
> alle elementari:
Poi succede che uno studia matematica anche alle medie, al liceo, alla
facolta', al dottorato, e si dimentica che si puo' scomporre in fattori
provando coi numeri dispari invece che coi numeri primi.
Cristiano
> D'altro canto, ad evitare il sospetto di spacconeria, mandami
> un programmino fatto di "qualche riga di programma per il
> crivello e qualche altra aggiuntiva per trovare i numeri primi..."
E a che servirebbe? Se ti dico che c'ho messo 3 minuti e tu sospetti che io
sia uno spaccone, stiamo perdendo tempo in due.
Continua a reputarmi uno spaccone; io ho cose più serie da fare.
Cristiano
Dalet
>Per fattorizzare i numeri maggiori di 2^31 bisogna aggiungere
>un cast nel test del for, cioe' p*(long long) p<=n invece di p*p<=n.
E minori di quanto? perche' Factor di Linux da riga di
comando arriva a 2^64, eccolo:
[~]dalet $: echo '2^64' | bc | factor
factor: `18446744073709551616' is too large
[~]dalet $: echo '2^64-1' | bc | factor
18446744073709551615: 3 5 17 257 641 65537 6700417
Si puo' battere?
--
Saluti, Dalet
Cristiano
> [~]dalet $: echo '2^64-1' | bc | factor
> 18446744073709551615: 3 5 17 257 641 65537 6700417
Quanto impiega per fornire quel risultato?
Cristiano
nano bagonghi
chiaramente per ottenere quel risultato ci mette
pochissimo (1 centesimo di secondo al massimo)
perche' una volta diviso per 65537 che e' il 6543-esimo
numero primo, poi il residuo (6700417) deve essere
primo per forza.
Il problema e' se invece a factor gli passi
un numero primo molto grosso, tipo il numero
primo che precede 2^64, ovvero
18446744073709551557
ci mette molto piu' tempo (sul mio pc circa 15 secondi)
perche' di fatto fa tentativi fino a raggiungere
la radice di quel numero che e' circa 2^32, ovvero
circa 4 miliardi. Fino a 4 miliardi ci sono circa 190 milioni
di numeri primi, quindi deve fare un bel po' di tentativi
prima di decidere che non ci sono divisori primi piu'
piccoli del numero stesso...
Poi in realta' tieni conto che factor non genera
i numeri primi quindi divide anche per numeri che
non sono primi. In particolare usa il meccanismo
denominato "wheel factorization"
http://primes.utm.edu/glossary/page.php?sort=WheelFactorization
per evitare di dividere per numeri che sono sicuramente
multipli di 2,3,5,7 e 11.
Il meccanismo e' piu' o meno questo:
se vuoi evitare di dividere per i numeri pari allora
parti da un divisore dispari (3) e ogni volta aggiungi 2.
Pero' in questo modo ottieni 3 5 7 11 13 15 ...
e 15 e' un multiplo di 3. Per evitare i multipli di 3
puoi partire da 5 e sommare alternativamente 2 e 4.
In questo modo salti automaticamente i multipli di 3.
Il metodo si puo' generalizzare e puoi costruire una tabella
(la cui dimensione chiaramente cresce piuttosto velocemente)
della sequenza ciclica di incrementi che ti permette
di saltare automaticamente dei divisori che certamente non
sono primi. Ecco, la versione corrente di factor
(mi sembra la 6.9 nelle GNU coreutils) usa una tabella di
incrementi per evitare i multipli di 2,3,5,7 e 11.
Se fare salti di 2 riduce il numero di tentativi
di un fattore 2 (50%, ne provi 1 ogni 2),
alternare incrementi di 2 e 4
riduce il numero di tentativi a 2 ogni 6,
cioe' al del 66.6%.
Analogamente, evitare con opportuni incrementi tutti i multipli
ovvi di 2,3,5,7,11 porta a considerare (2-1)(3-1)(5-1)(7-1)(11-1) = 480
divisori su 2*3*5*7*11=2310, quindi a ridurli del 79% circa.
Nonostante questo factor rimane un programma abbastanza
rudimentale (comunque basato sui ripetuti tentativi
di divisione): va benissimo per numeri piccoli
ma per numeri grandini (come quel numero primo citato
sopra o per un numero che sia per esempio il prodotto di due numeri
primi entrambi vicini a 2^32) mostra i suoi limiti.
Quando la divisione a tentativi non basta piu' esistono
sistemi piu' sofisticati (rho di Pollard, curve ellittiche, etc.etc.)
oltre a qualche test di primalita' probabilistico per capire
quando e' il caso di fermarsi.
ciao,
g.
Dalet
>Dalet wrote:
[~]dalet $: time echo '2^64-1' | bc | factor
18446744073709551615: 3 5 17 257 641 65537 6700417
real 0m0.003s
user 0m0.000s
sys 0m0.000s
su macchina:
[~]dalet $: uname -a
Linux p915 2.6.18-5-686 #1 SMP Wed Oct 3 00:12:50 UTC 2007 i686 GNU/Linux
[~]dalet $: cat /proc/cpuinfo
processor : 0
vendor_id : GenuineIntel
cpu family : 15
model : 6
model name : Intel(R) Pentium(R) D CPU 2.80GHz
stepping : 4
cpu MHz : 2792.394
cache size : 2048 KB
physical id : 0
siblings : 2
core id : 0
cpu cores : 2
fdiv_bug : no
hlt_bug : no
f00f_bug : no
coma_bug : no
fpu : yes
fpu_exception : yes
cpuid level : 6
wp : yes
bogomips : 5589.85
processor : 1
vendor_id : GenuineIntel
cpu family : 15
model : 6
model name : Intel(R) Pentium(R) D CPU 2.80GHz
stepping : 4
cpu MHz : 2792.394
cache size : 2048 KB
physical id : 0
siblings : 2
core id : 1
cpu cores : 2
fdiv_bug : no
hlt_bug : no
f00f_bug : no
coma_bug : no
fpu : yes
fpu_exception : yes
cpuid level : 6
wp : yes
bogomips : 5585.14
--
Saluti, Dalet
nano bagonghi
> Il 19-12-2007, nano bagonghi dice:
>
>
>>Per fattorizzare i numeri maggiori di 2^31 bisogna aggiungere
>>un cast nel test del for, cioe' p*(long long) p<=n invece di p*p<=n.
>
>
> E minori di quanto? perche' Factor di Linux da riga di
> comando arriva a 2^64, eccolo:
cambiando opportunamente i tipi in unsigned long long
(che tipicamente in gcc sono implementati con almeno 64 bit)
si puo' arrivare allo stesso limite di factor.
Anche perche' il metodo che usa factor e' comunque sempre
un metodo a divisioni ripetute. Factor e' piu'
veloce del mio programmillo perche' evita di dividere
per i multipli di 2,3,5,7 e 11 (vedi l'altro mio messaggio).
> Si puo' battere?
Certamente si puo' battere. Pero' bisogna usare una libreria
per i numeri in precisione arbitraria, tipo la GMP della gnu,
(o un linguaggio che supporti direttamente gli interi in
precisione arbitraria)
e poi per trattare numeri maggiori di 2^64 senza avere tempi
potenzialmente anche molto lunghi bisogna cambiare proprio
metodo. Purtroppo i metodi avanzati non sono proprio
immediati da comprendere o implementare. Per esempio,
sul sito
http://www.alpertron.com.ar/ECM.HTM
c'e' on-line una applet per fattorizzare col metodo
delle curve ellittiche (attenzione, crea dipendenza!).
Per dare una idea,
la fattorizzazione di
680564733841876929149581875745537392901
con il programma di Alpern si trova in meno di un secondo
(9223372036854775837 * 73786976294838206473)
ciao,
g.
Dalet
>Il problema e' se invece a factor gli passi
>un numero primo molto grosso, tipo il numero
>primo che precede 2^64, ovvero
>18446744073709551557
>ci mette molto piu' tempo (sul mio pc circa 15 secondi)
[~]dalet $: time factor 18446744073709551557
18446744073709551557: 18446744073709551557
real 1m3.885s
user 1m3.888s
sys 0m0.000s
Accidenti! 1 minuto e quasi 4 secondi! ma che macchina
c'hai tu per metterci solo 15"?
Ma mi sa tanto che da me va con una sola cpu anche
se il kernel e' compilato per smp.
Ps. Ho letto adesso il tuo reply: interessante, TNX delle
info.
--
Saluti, Dalet
nano bagonghi
> Accidenti! 1 minuto e quasi 4 secondi! ma che macchina
> c'hai tu per metterci solo 15"?
per la precisione su una:
real 0m18.014s
user 0m17.993s su
model name : Intel(R) Pentium(R) D CPU 3.20GHz
cpu MHz : 2800.000
e sull'altra:
real 0m13.760s
user 0m13.761s
model name : Intel(R) Core(TM)2 CPU 6600 @ 2.40GHz
nel tuo caso tieni presente che se anche hai come me un
processore dual core,
factor non e' pensato per usare piu thread, quindi
non ne puo' trarre beneficio direttamente.
Infatti nel tuo caso i due tempi real e user sono
praticamente uguali, segno che il processo sta usando
al 100% un core, e piu' di tanto non puo' fare.
Certo un minuto e' tantino, considerando che sul mio
portatile winXP che ha un AMD Athlon(tm) 64 Processor 3400+ (2.2Ghz)
sotto cygwin ci mette circa 48 secondi.
ciao,
g.
Bruno Campanini
> Volevo aggiungere (oltre al mio nome e cognome in calce,
> visto che qui ci si giocavano i gioielli di famiglia :-) )
> che quello che ho postato funziona a linea di comando,
> cioe' uno scrive per esempio
> pippo 123456789
> e quello stampa i fattori ovvero 3 3 3607 3803
> Per fattorizzare i numeri maggiori di 2^31 bisogna aggiungere
> un cast nel test del for, cioe' p*(long long) p<=n invece di p*p<=n.
> E volevo aggiungere anche che il programmino
> funziona, ma e' stato pensato per essere scritto in velocita',
> non per essere particolarmente performante.
> A programmare un crivello, per quanto sia una cosa piuttosto facile,
> ci avrei messo sicuramente di piu'.
> Io non sono un programmatore, ma bene o male sono piu'
> di 25 (acc!) anni che programmicchio.
Ok - salvis coglionibus - tutto chiaro.
Anch'io è da un po' che bazzico coi computer - middle seventies.
Avendo iniziato già da prima con l'RPN dell'HP.
Ciao
Bruno
PS
Circa il nome e cognome.
Nella mia personalissima classifica acquista posizioni
chi non si "nasconde" dietro pseudonimo (o dovrei dire
nick name?).
Ma la mia è una classifica molto, molto personale...
Cristiano
> Cristiano wrote:
>
>> Dalet wrote:
>>
>>> [~]dalet $: echo '2^64-1' | bc | factor
>>> 18446744073709551615: 3 5 17 257 641 65537 6700417
>>
>>
>> Quanto impiega per fornire quel risultato?
>
> chiaramente per ottenere quel risultato ci mette
> pochissimo (1 centesimo di secondo al massimo)
> perche' una volta diviso per 65537 che e' il 6543-esimo
> numero primo, poi il residuo (6700417) deve essere
> primo per forza.
Non sono un drago in matematica; perché deve essere primo per forza?
> Il problema e' se invece a factor gli passi
> un numero primo molto grosso, tipo il numero
> primo che precede 2^64, ovvero
> 18446744073709551557
> ci mette molto piu' tempo (sul mio pc circa 15 secondi)
> [...]
Ma č ancora buono, perché utilizzando un crivello quadratico ("primegen",
scritto dal mitico Bernstein) il mio PC (con CPU simile alla tua: E6400 a
2,4 GHz) impiega 10,8 s.
> Quando la divisione a tentativi non basta piu' esistono
> sistemi piu' sofisticati (rho di Pollard, curve ellittiche, etc.etc.)
> oltre a qualche test di primalita' probabilistico per capire
> quando e' il caso di fermarsi.
MR primo tra tutti! :-)
Per la fattorizzazione, invece, utilizzo PPSIQS (un crivello quadratico
auto-inizializzante), il piů veloce programma che abbia mai visto di
fattorizzazione generica (da utilizzare, cioč per numeri che non hanno una
particolare forma o struttura).
Cristiano
nano bagonghi
> nano bagonghi wrote:
>>>Quanto impiega per fornire quel risultato?
>>
>>chiaramente per ottenere quel risultato ci mette
>>pochissimo (1 centesimo di secondo al massimo)
>>perche' una volta diviso per 65537 che e' il 6543-esimo
>>numero primo, poi il residuo (6700417) deve essere
>>primo per forza.
>
> Non sono un drago in matematica; perché deve essere primo per forza?
perche' se 6700417 non e' primo, deve avere un
fattore minore o uguale alla radice di 6700417.
Ma la radice di 6700417 e' sicuramente minore del divisore 65537 al
quale sono arrivato, quindi se 6700417 fosse composto avrei
gia' trovato dei suoi fattori. Siccome non e' cosi', allora e' primo.
> Ma è ancora buono, perché utilizzando un crivello quadratico ("primegen",
> scritto dal mitico Bernstein) il mio PC (con CPU simile alla tua: E6400 a
> 2,4 GHz) impiega 10,8 s.
Anche io di solito uso primegen.
> Per la fattorizzazione, invece, utilizzo PPSIQS (un crivello quadratico
questo non lo conosco, casomai ci do una occhiata.
ciao,
g.
Lorents
> Scusate la mia assoluta ignoranza in materia, conoscete uno strumento
> senza essere collegati a internet) per effettuare la scomposizione di
> un numero in fattori primi? Potrebbe andare bene anche Excel o Calc,
> se mi dite che esiste una funzione apposita...
Prova a scaricare factor.exe da
http://www.shamus.ie/index.php?page=Other-Features