Algoritmi - SFIDA: Chi posta il numero primo più alto?

beh geniale.. se fossi nato circa 2300 anni fa... in pratica stai parlando del crivello di eratostene!

cmq l'algoritmo attualmente migliore è il "number field sieve", cioè il crivello del campo numerico.

Beh... mica ho mai detto di averlo inventato io, semplicemente e' quello che mi e' venuto in mente.



Non lo conosco, mi informero'

Ciao.

e se invece di:
-prendo un numero n di cui voglio stabilire la primalità (sidice così?)
-divido n per tutti e soli i numeri maggiori di 1 e minori di radice di n

faccio cosi:

-prendo un numero n di cui voglio stabilire la primalità (sidice così?)
-guardo se il numero è divisibile per 2, se si allora niente, se no aumento il passo di 1 in modo tale da eliminare il controllo di tutti i numeri pari dimezzando di netto i confronti da fare

(poi una cosa del genere si potrebbe anche fare per multipli di 3, sapendo che un numero è divisibile per 3 se la somma delle loro cifre è multipla di 3, però non so se ci si guadagna o perde in velocità

ci avevo gia pensato,anzi ho scritto un programma in python per i vari criteri di divisibilità (2,3,11,13,17,10n-1), il punto è che molti criteri richiedono di fare somme di cifre e questo comporta la trasformazione dell'intero in stringa per poter ottenere le cifre da ritrasformare in intero. Tutto questo causa una bella perdita di tempo

esempio:

def d3(n):
	global s
	somma = 0
	for i in str(n):
		somma += int(i)
	if somma > 9:
		d3(somma)
	else:
		if somma>=3 and somma%3 == 0: s = False # e' divisibile per 3		

sicuramente a velocità fa schifo ma l'unica cosa che mi è passato x il cervello è questa:

int primo=0,verifica;

 while(1)
            {
            verifica=0;
            for(int i=1;i<primo;i++)
                    {
                    if(primo%i==0)
                      verifica++;
                    }
            if(verifica<2)
               {
               cout<<primo<<"\n";
               }
            primo++;
            }

praticamente conto tutte le volte che è stato possibile dividere. siccome i numeri primi possono essere divisi solo x se stessi e per uno il numero massimo di volte che sono stati divisi deve essere quindi inferiore a 2
sicuramente questo è l'algoritmo + lento del mondo x questo tipo di problema!


edit: con questo algoritmo inizialndolo a 81110000 in 5 minuti ha prodotto solo 6 risultati:
81110023
81110027
81110039
81110041
81110047
81110059
confermo che è l'algoritmo + lento del mondo

Con 1 ora di elaborazione, sono riuscito a trovare questo numero che spero sia primo.
Ho fatto un test probabilistico e quindi c'è la possibilità, che è molto piccola, che quel numero non sia primo

in un test probabilistico la possibilità è più alta di quanto si pensa...

La possibilità che il numero non sia primo è circa 1/(2x10^-148)