[C con Clase] Pregunta Primo

[Mariano Demarchi]

De hecho basta con llegar hasta el siguiente de la parte entera de la raíz.
También puede ser interesante hacer el algoritmo que calcula los primeros
números primos, dinámico, algo así (no se si compila, pero creo que la
lógica es correcta):

int primos[MAXP];
int pprimos;

int main()
{
int i = 3;
int j;
pprimos = 1;
primos[0] = 2;
primos[1] = 3;
while(cprimos<MAXP){
 i += 2;
for(j=1;j<=cprimos;j++)
if(i % primos[j])
if(j==cprimos)
primos[++cprimos] = i;
else continue;

}
return 0;
}

Pero mas rápido es la criba de Erastotenes:


char primos[MAXP];

int main()
{
long p;
long i;
for(i=2;i<=MAXP;i++)
primos[i] = 1;
for(i=2;i<=MAXP;i++){
 p = i;
while((p += i) <= MAXP)
primos[p] = 0;
}
return 0;
}*/





El 10 de noviembre de 2009 04:25, Jose Cabrera <josmaca en gmail.com> escribió:

> El problema de la criba es que es para buscar numeros primos, no para
> deducir si un número en concreto es primo, que alomejor es más eficiente
> hacer la criba hasta llegar al que nos interesa.
> A otra cosa que queria comentar y que antes se me olvido es que no hace
> falta llegar hasta n-1 para deducir si es primo solo hay que llegar hasta
> n/2, asi tardas la mitad.
>
> El 9 de noviembre de 2009 23:37, Kalith <kalith en kernelerror.net> escribió:
>
>>  lo que Jose Cabrera dice es lo que yo dije antes probar todos los numeros
>> ejemplo:--
>>
>>
>> #include <iostream>
>>>
>>> int main(void){
>>>
>>>     size_t n, con = 0;
>>>
>>>     std::cin >> n;
>>>
>>>     for(size_t i = 2; i <= n; ++i)
>>>         if(!(n % i)) ++con;
>>>
>>>     if(con == 1) std::cout << n << " es primo.!" << std::endl;
>>> }
>>>
>>
>> pero no es algo eficiente, lo mas eficiente es generar una criba de
>> eratostenes a mi parecer y de ahi comprobar.
>>
>>
>>
>> Linux Counter User #487374
>>
>> Está en contra de los fundamentos de la educación moderna enseñar a
>> programar a los niños. ¿Qué diversión hay en hacer planes, en adquirir
>> disciplina para organizar los pensamientos, en dedicarle atención al
>> detalle, y en aprender a ser autocrítico?
>>
>> _______________________________________________
>> Lista de correo Cconclase Cconclase en listas.conclase.net
>> http://listas.conclase.net/mailman/listinfo/cconclase_listas.conclase.net
>> Bajas: http://listas.conclase.net/index.php?gid=2&mnu=FAQ
>>
>
>
> _______________________________________________
> Lista de correo Cconclase Cconclase en listas.conclase.net
> http://listas.conclase.net/mailman/listinfo/cconclase_listas.conclase.net
> Bajas: http://listas.conclase.net/index.php?gid=2&mnu=FAQ
>
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://listas.conclase.net/pipermail/cconclase_listas.conclase.net/attachments/20091111/c04a1b16/attachment.html>