Algoritmi sui numeri primi.

Il ritrovo della comunità dove confrontarsi e discutere sulle notizie dal mondo dell'informatica, di Ubuntu e di tutto quello che la riguarda, novità, pettegolezzi e quant'altro.
P_1_6
Prode Principiante
Messaggi: 20
Iscrizione: giovedì 25 dicembre 2014, 23:01
Distribuzione: Ubuntu 15.10 i686

Algoritmi sui numeri primi.

Messaggio da P_1_6 »

Avatar utente
Zoff
Moderatore Globale
Moderatore Globale
Messaggi: 33338
Iscrizione: mercoledì 10 ottobre 2007, 22:36

Re: Algoritmi sui numeri primi.

Messaggio da Zoff »

Non è che si sia nulla di nuovo, non mi è chiara quindi la "creazione" dove sta, anzi l'assunzione è imprecisa perché non vale solo per i numeri primi e non viene dimostrata.

È stato già ampiamente dimostrato che qualsiasi numero (anche non primo) maggiore di 3 è esprimibile nella forma 6n+1 o 6n-1 se non divisibile da 2 o 3.
Questo significa quindi che ogni numero maggiore di 3 non divisibile per 2 o 3 si trova immediatamente dopo o immediatamente prima o immediatamente dopo ad un numero multiplo di 6.

DIMOSTRAZIONE (che nei tuoi articoli hai dimenticato di indicare)
Prendiamo l'espressione:
n = 6q + r
n è un qualsiasi numero
q è il quoziente della divisione per 6 di n
r è il resto della divisione per 6 di n

I valori di r possibili sono 0, 1, 2, 3, 4, 5.
Nella tua definizione hai escluso 0, 2 e 3 perché renderebbero il numero divisibile per 2 o 3.
I resti possibili rimanenti sono 1 e 5, da quì i decimali periodici: 1/6=0.16p e 5/6=0.83p
Prima di aprire una discussione leggi le Guide, poi vedi se c'è un HowTo nel Wiki e fai una ricerca nel Forum!
Applica semplicemente il [Risolto]! Prova: http://forum.ubuntu-it.org/viewtopic.php?f=70&t=548821
Vuoi qualcosa di piu' dal forum? Prova i miei script: http://forum.ubuntu-it.org/viewtopic.php?f=70&t=597066
P_1_6
Prode Principiante
Messaggi: 20
Iscrizione: giovedì 25 dicembre 2014, 23:01
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggio da P_1_6 »

grazie per la tua risposta.
Veramente non conoscevo questa cosa ma l'ho applicata lo stesso.
quindi il crivello già esisteva e sotto quale nome?
così me lo studio.
Avatar utente
Zoff
Moderatore Globale
Moderatore Globale
Messaggi: 33338
Iscrizione: mercoledì 10 ottobre 2007, 22:36

Re: Algoritmi sui numeri primi.

Messaggio da Zoff »

L'ha espresso in termini differenti anche eulero nei suoi teoremi: http://mathworld.wolfram.com/Eulers6nPlus1Theorem.html
Prima di aprire una discussione leggi le Guide, poi vedi se c'è un HowTo nel Wiki e fai una ricerca nel Forum!
Applica semplicemente il [Risolto]! Prova: http://forum.ubuntu-it.org/viewtopic.php?f=70&t=548821
Vuoi qualcosa di piu' dal forum? Prova i miei script: http://forum.ubuntu-it.org/viewtopic.php?f=70&t=597066
P_1_6
Prode Principiante
Messaggi: 20
Iscrizione: giovedì 25 dicembre 2014, 23:01
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggio da P_1_6 »

quindi il crivello di atkin non è attualmente il più veloce metodo per trovare tutti i primi fino ad n?
Avatar utente
Zoff
Moderatore Globale
Moderatore Globale
Messaggi: 33338
Iscrizione: mercoledì 10 ottobre 2007, 22:36

Re: Algoritmi sui numeri primi.

Messaggio da Zoff »

Mi sembra di ricordare che Atkin resta l'algoritmo piu' veloce.
Ovviamente l'implementazione è sempre da tenere in conto.

Se ti capita di trovare un modo veramente veloce per generare i numeri primi puoi vincere anche 150.000$: https://www.eff.org/awards/coop
Prima di aprire una discussione leggi le Guide, poi vedi se c'è un HowTo nel Wiki e fai una ricerca nel Forum!
Applica semplicemente il [Risolto]! Prova: http://forum.ubuntu-it.org/viewtopic.php?f=70&t=548821
Vuoi qualcosa di piu' dal forum? Prova i miei script: http://forum.ubuntu-it.org/viewtopic.php?f=70&t=597066
P_1_6
Prode Principiante
Messaggi: 20
Iscrizione: giovedì 25 dicembre 2014, 23:01
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggio da P_1_6 »

grazie.
ma potresti dirmi una cosa
seconde te nel frattempo che atkin mette n false al vettore
il mio gia ha trovato i p fino ad n?
Avatar utente
Zoff
Moderatore Globale
Moderatore Globale
Messaggi: 33338
Iscrizione: mercoledì 10 ottobre 2007, 22:36

Re: Algoritmi sui numeri primi.

Messaggio da Zoff »

Secondo me no, le operazioni in virgola mobile hanno una complessità maggiore e sono meno precise di quelle in numeri interi.
Potrei scrivere una cavolata vista l'ora ma non credo che esistano algoritmi di generazione di numeri primi esatti che utilizzano operazioni in virgola mobile.

Vedi: http://en.wikipedia.org/wiki/Prime_numb ... ime_number
Prima di aprire una discussione leggi le Guide, poi vedi se c'è un HowTo nel Wiki e fai una ricerca nel Forum!
Applica semplicemente il [Risolto]! Prova: http://forum.ubuntu-it.org/viewtopic.php?f=70&t=548821
Vuoi qualcosa di piu' dal forum? Prova i miei script: http://forum.ubuntu-it.org/viewtopic.php?f=70&t=597066
P_1_6
Prode Principiante
Messaggi: 20
Iscrizione: giovedì 25 dicembre 2014, 23:01
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggio da P_1_6 »

Nell’implementazione al posto dei periodici per sei si possono utilizzare i numeri che partendo da 5 fanno una volta +2 una volta +4.
Cioè 5 , 5+2=7 , 7+4=11 ,11+2=13 , 13+4=17 , ecc, ecc.
Può essere sviluppato in molte meno operazioni matematiche di n/3 +(n/3)-p ma sempre maggiori di n/3.
Alberico Lepore 22 dicembre 2014
si trovava in fondo alla spiegazione
Avatar utente
Zoff
Moderatore Globale
Moderatore Globale
Messaggi: 33338
Iscrizione: mercoledì 10 ottobre 2007, 22:36

Re: Algoritmi sui numeri primi.

Messaggio da Zoff »

Non credo di aver capito cosa intendi.

5 , 5+2=7 , 7+4=11 ,11+2=13 , 13+4=17, 17+2=19, 19+4=25 (NON PRIMO!)
Prima di aprire una discussione leggi le Guide, poi vedi se c'è un HowTo nel Wiki e fai una ricerca nel Forum!
Applica semplicemente il [Risolto]! Prova: http://forum.ubuntu-it.org/viewtopic.php?f=70&t=548821
Vuoi qualcosa di piu' dal forum? Prova i miei script: http://forum.ubuntu-it.org/viewtopic.php?f=70&t=597066
P_1_6
Prode Principiante
Messaggi: 20
Iscrizione: giovedì 25 dicembre 2014, 23:01
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggio da P_1_6 »

dai non scherzare.
secondo te è una cosa buona o no?
Avatar utente
Zoff
Moderatore Globale
Moderatore Globale
Messaggi: 33338
Iscrizione: mercoledì 10 ottobre 2007, 22:36

Re: Algoritmi sui numeri primi.

Messaggio da Zoff »

Boh, io non scherzo. Non ho capito come trasformi in calcoli interi l'algoritmo e quante sono le operazioni dopo la trasformazione.
Prima di aprire una discussione leggi le Guide, poi vedi se c'è un HowTo nel Wiki e fai una ricerca nel Forum!
Applica semplicemente il [Risolto]! Prova: http://forum.ubuntu-it.org/viewtopic.php?f=70&t=548821
Vuoi qualcosa di piu' dal forum? Prova i miei script: http://forum.ubuntu-it.org/viewtopic.php?f=70&t=597066
P_1_6
Prode Principiante
Messaggi: 20
Iscrizione: giovedì 25 dicembre 2014, 23:01
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggio da P_1_6 »

allora tu non vuoi farmi andare a letto comunque
vediamo fino a 100 sono 32 operazioni di questo
5 , 5+2=7 , 7+4=11 ,11+2=13 , 13+4=17, 17+2=19, 19+4=25 (NON PRIMO!)
i non primi li togli così
5*5; 25+30 ; 55+30;
5*7;35+30 ; 65+30;
7*7; 49+42;
7*11;
come avevo scritto qui
Nell’implementazione nell’eliminazione degli scarti si deve tener presente che per ogni numero primo ps gli scarti associati sono
s1=ps^2 ; s2=s1 + ps*6; s3=s2+ps*6; ecc.
e
sm1=ps*ps+1; sm2=sm1 + ps*6; sm3=sm2+ps*6; ecc. dove ps+1 è il primo successivo
però si devono saltare i non primi fino alla radice quadrata di n quindi
(radice quadrata di n)/3-p1 dove p1 è il numero dei primi fino a (radice quadrata di n).

Alberico Lepore 25 dicembre 2014
in effetti avevo mancato il fratto 3
comunque in totale sono in questo caso sono 34 operazioni
p.s. scusami se sbaglio qualcosa
-------------------------------------------------------------------------------------------------------------------------------------------------------------
stavo scherzando sono 42 + l'aggiunta del 2 e del 3 che sono una costante
quindi in totale sono 44 operazioni
-----------------------------------------------------------------------------------------------------------------------------------------------------------

diciamo pure +5 se vogliamo metterci i capolinea

---------------------------------------------------------------------------------------------------------------------------------------------------------
diciamo pure +2 per fare 6*5 e 6*7
---------------------------------------------------------------------------------------------------------------------------------------------------------
Avatar utente
Zoff
Moderatore Globale
Moderatore Globale
Messaggi: 33338
Iscrizione: mercoledì 10 ottobre 2007, 22:36

Re: Algoritmi sui numeri primi.

Messaggio da Zoff »

Boh, a me sembra che tu stia andando a casaccio. Ogni tanto aggiungi un pezzo o ne cambi un altro.
Magari un giorno quando farai una descrizione formale e precisa dell'algoritmo ci riguarderò.

Buon natale!
Prima di aprire una discussione leggi le Guide, poi vedi se c'è un HowTo nel Wiki e fai una ricerca nel Forum!
Applica semplicemente il [Risolto]! Prova: http://forum.ubuntu-it.org/viewtopic.php?f=70&t=548821
Vuoi qualcosa di piu' dal forum? Prova i miei script: http://forum.ubuntu-it.org/viewtopic.php?f=70&t=597066
P_1_6
Prode Principiante
Messaggi: 20
Iscrizione: giovedì 25 dicembre 2014, 23:01
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggio da P_1_6 »

secondo voi è una cosa buona o no?
P_1_6
Prode Principiante
Messaggi: 20
Iscrizione: giovedì 25 dicembre 2014, 23:01
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggio da P_1_6 »

ma non c'è nessun altro in questo forum?
Avatar utente
Mdfalcubo
Moderatore Globale
Moderatore Globale
Messaggi: 20415
Iscrizione: venerdì 26 dicembre 2008, 11:17
Desktop: Solo XFCE
Distribuzione: Xubuntu 64 bit
Sesso: Maschile

Re: Algoritmi sui numeri primi.

Messaggio da Mdfalcubo »

Siamo sotto le feste, la gente forse ha di meglio da fare non credi? Poi ti è già stato risposto in maniera piuttosto chiara e dettagliata mi pare.
"Il genere umano è stimolante, è la gente che non sopporto,, (Linus - Peanuts)
P_1_6
Prode Principiante
Messaggi: 20
Iscrizione: giovedì 25 dicembre 2014, 23:01
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggio da P_1_6 »

scusami per l'insistenza.
poi non mi sembra chiara e dettagliata la risposta.
P_1_6
Prode Principiante
Messaggi: 20
Iscrizione: giovedì 25 dicembre 2014, 23:01
Distribuzione: Ubuntu 15.10 i686

possibile decodifica RSA.

Messaggio da P_1_6 »

Di questo che ne pensate?


X=fattore primo(incognita)

X^2+n(X*6)=numero rsa
per n che va da 1 a fino a quando non l'hai decodificato
e X che appartiene a quell'insieme di 5 , 5+2=7 , 7+4=11 ,11+2=13 , 13+4=17, 17+2=19, 23+2=25 25+4=29 ecc oppure se vi è piu facile capire
0,8333 ; 1,1666 ;1,8333 ; 2,1666 ; ecc questi moltiplicati per 6
P_1_6
Prode Principiante
Messaggi: 20
Iscrizione: giovedì 25 dicembre 2014, 23:01
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggio da P_1_6 »

L'altro pezzo lo avete capito?
Scrivi risposta

Ritorna a “Bar Ubuntu”

Chi c’è in linea

Visualizzano questa sezione: Sannythebest e 17 ospiti