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):<br>
<br>int primos[MAXP];<br>int pprimos;<br>
<br>int main()<br>{<br><div style="margin-left:40px">int i = 3;<br>int j;<br>pprimos = 1;<br></div><div style="margin-left:40px">primos[0] = 2;<br>primos[1] = 3;<br>while(cprimos<MAXP){<br><div style="margin-left:40px">
i += 2;<br>for(j=1;j<=cprimos;j++)<br><div style="margin-left:40px">if(i % primos[j]) <br><div style="margin-left:40px">if(j==cprimos)<br><div style="margin-left:40px">primos[++cprimos] = i;<br></div></div></div></div>
</div><div style="margin-left:120px">else continue; <div><br></div></div><div style="margin-left:40px">}<br><div style="margin-left:40px"><div style="margin-left:40px">
</div></div></div><div style="margin-left:40px">return 0;<br></div>}<br><br>Pero mas rápido es la criba de Erastotenes:<br><br><div><br>char primos[MAXP];</div><div><br></div><div><div>int main()</div><div>{</div><div style="margin-left:40px">
long p;</div><div style="margin-left:40px"> long i;</div><div style="margin-left:40px"> for(i=2;i<=MAXP;i++)</div><div style="margin-left:80px"> primos[i] = 1;</div><div style="margin-left:40px"> for(i=2;i<=MAXP;i++){</div>
<div style="margin-left:80px"> p = i;</div><div style="margin-left:80px"> while((p += i) <= MAXP)</div><div style="margin-left:80px">primos[p] = 0;<br></div><div style="margin-left:40px">}</div><div style="margin-left:40px">
return 0;</div><div>}*/</div><div><br></div><div><br></div></div><div><br></div><div><br></div><br><div class="gmail_quote">El 10 de noviembre de 2009 04:25, Jose Cabrera <span dir="ltr"><<a href="mailto:josmaca@gmail.com" target="_blank">josmaca@gmail.com</a>></span> escribió:<br>
<blockquote class="gmail_quote" style="border-left:1px solid rgb(204, 204, 204);margin:0pt 0pt 0pt 0.8ex;padding-left:1ex">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.<br>
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.<br>
<br><div class="gmail_quote">El 9 de noviembre de 2009 23:37, Kalith <span dir="ltr"><<a href="mailto:kalith@kernelerror.net" target="_blank">kalith@kernelerror.net</a>></span> escribió:<br><blockquote class="gmail_quote" style="border-left:1px solid rgb(204, 204, 204);margin:0pt 0pt 0pt 0.8ex;padding-left:1ex">
<div><div>
lo que Jose Cabrera dice es lo que yo dije antes probar todos los numeros ejemplo:-- <br><br><br><blockquote style="border-left:1px solid rgb(204, 204, 204);margin:0pt 0pt 0pt 0.8ex;padding-left:1ex" class="gmail_quote">
#include <iostream><br><br>int main(void){<br><br> size_t n, con = 0;<br><br> std::cin >> n;<br><br> for(size_t i = 2; i <= n; ++i)<br> if(!(n % i)) ++con;<br><br> if(con == 1) std::cout << n << " es primo.!" << std::endl;<br>
}<br></blockquote><br>pero no es algo eficiente, lo mas eficiente es generar una criba de eratostenes a mi parecer y de ahi comprobar.<div><div><br><br><br>Linux Counter User #487374<br><br>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?<br>
</div></div><br></div></div><div>_______________________________________________<br>
Lista de correo Cconclase <a href="mailto:Cconclase@listas.conclase.net" target="_blank">Cconclase@listas.conclase.net</a><br>
<a href="http://listas.conclase.net/mailman/listinfo/cconclase_listas.conclase.net" target="_blank">http://listas.conclase.net/mailman/listinfo/cconclase_listas.conclase.net</a><br>
Bajas: <a href="http://listas.conclase.net/index.php?gid=2&mnu=FAQ" target="_blank">http://listas.conclase.net/index.php?gid=2&mnu=FAQ</a><br></div></blockquote></div><br>
<br>_______________________________________________<br>
Lista de correo Cconclase <a href="mailto:Cconclase@listas.conclase.net" target="_blank">Cconclase@listas.conclase.net</a><br>
<a href="http://listas.conclase.net/mailman/listinfo/cconclase_listas.conclase.net" target="_blank">http://listas.conclase.net/mailman/listinfo/cconclase_listas.conclase.net</a><br>
Bajas: <a href="http://listas.conclase.net/index.php?gid=2&mnu=FAQ" target="_blank">http://listas.conclase.net/index.php?gid=2&mnu=FAQ</a><br></blockquote></div><br>