Algoritmi sui numeri primi.

[P_1_6]

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

[P_1_6]

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.

[P_1_6]

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

[P_1_6]

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.

[P_1_6]

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

Dai @Zoff

[P_1_6]

Adesso dovrebbe essere corretto

[P_1_6]

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

[P_1_6]

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

[P_1_6]

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

[P_1_6]

#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

[P_1_6]

https://www.academia.edu/121400171/Siev ... y_interval