Forum Ubuntu-it

reiterando e ricordandosi di scrivere m in funzione di a e b e testando per m=0 e b=5 ed m=2 e b=7
solve m=0 , b=5 , [[sqrt(117-n*a)+1]/2]^2-(m/2)^2=[a*b- (2 +2*(b-1))*(b-1)/2] , b=[sqrt(117-n*a)+1]/2-m/2 , a=sqrt(117-n*a) , a^2+n*a=117

Hey admin
mi fate sapere qualcosa anche se la risposta è negativa.
Ho fatto dei calcoli teorici ed un numero di 100 cifre viene fattorizzato in poco più di 300 step
E' tutto vero datemi un opportunità.
Ciao.

ormai l'ho pubblicato solo che sbagliavo è in O([log_9(N)]^3)
https://www.academia.edu/35412746/Test_ ... _log_9_N_3_

Hey amici potreste dare uno sguardo?
Che ne pensate?

EDIT
Testing m, r, s, t, v, z,

n-m=1
m-r=1
r-s=1
s-t=1
t-v=1
v-z=1
etc.etc.

ragazzi qualcuno che lo implementi c'è?
E' in O(log_2())

Dai @Zoff

Adesso dovrebbe essere corretto

Algoritmo di Natale
17° Test di primalità e fattorizzazione di Lepore

mi dispiace aver sbagliato.
il tempo impiegato è 2^x dove x è la profondità dell'albero.
x dipende da come è composto il numero e non dalla dimensione delle cifre

Questa è la volta buona
https://www.academia.edu/36782326/Fatto ... _4_O_log_n_

#C #gmplibrary

Nuovo #Crivello sui #numeriPrimi in un qualsiasi intervallo

Gentilmente mi dareste qualche feedback su come migliorare il sorgente?

se p è un primo nella forma 12*x+5
allora questa scrittura
36*m^2+18*m+4*n^2+2*n+3=(p+1)/2
è unica con n ed m in Z
ed ho la dimostrazione

Congettura
se 12*x+5 non è primo
o non ci sono soluzioni
o ha più di una soluzione
o se ne ha una mcd(4*n+1,4*m+1)!=1


Credo la migliore implementazione possibile sia:
- prendo due numeri min e max in input (che sono le estremità dell'intervallo I dove voglio cercare primi)
- creo una matrice M[(max-min)/12][3] e la inizializzo a 0
- mi calcolo l'intervallo di m e per ogni m mi calcolo l'intervallo di n
- quindi per ogni coppia (m,n) nei rispettivi range mi calcolo P=2*d-1=2*(36*m^2+18*m+4*n^2+2*n+3)-1
- vado ad incrementare di 1 M[(P-min)/12][0] ,
-se è la prima volta memorizzo m in M[(P-min)/12][1] , memorizzo n in M[(P-min)/12][2]
- quando ho finito scorrerò la matrice e se questo valore M[0] == 1 farò GCD(4*(M[1])+1,4*(M[2])+1) e se GCD ==1 stamperò P=min+12*i



L'ho implementato in C con la libreria gmp-6.3.0 in questo modo:
al posto della matrice M ho creato tre array e li ho chiamati
M[][0] -> occurrences[]
M[][1] -> m[]
M[][2] -> n[]

prende un numero da input.txt
che è il minimo dell'intervallo definito da
#define interval_size 100 (cioè vede se 100 elementi nella forma 12*x+5 sono primi [si può anche incrementare interval_size])
e restituisce tutti i primi nella forma 12*x+5 in quell'intervallo
mi scuso se non ho usato allocazione dinamica della memoria

https://github.com/Piunosei/lepore_sieve_4/tree/main


la complessità dell'algoritmo che ho scritto è O(sqrt(max_interval)) in particolare è (sqrt(2*max_interval-1)-3)/6*J+a*GCD dove J in media è un po più grande di uno [a certe condizioni], dove a sono i potenziali primi che si scrivono in modo unico e GCD il tempo per il calcolo del massimo comun divisore

E' vero il tempo dell'algoritmo AKS è O((log p)^6) però per trovarne uno mentre per l'algoritmo che ho scritto io o ne trovi uno o 100000 è sempre O(sqrt(max_interval)) cambia poco [vedi immagini]

Quindi sqrt(p)<C*(log p)^6 dove C è il numero di interval_size si ha che se scegliamo C>sqrt(p)/[(log p)^6] il mio crivello è più veloce di AKS