RE:Numeros primos en Turbo C++
Esa es la idea básica, pero puede optimizarse.
Un número es primo si solo se puede dividir por 1 y por él mismo. A si es que la solución de Jose Luis es probar a dividir con todos los números entre 1 y él mismo, y si se encuentra uno que lo divida, el número no será primo.
El problema es que se hacen más divisiones de las necesarias. Por ejemplo, un número no será divisible por 6 si no lo ha sido por 2, ni por 3 (2·3=6). A si es que probar si es divisible por 6 después de haber probado por 2 y por 3 es perder el tiempo.
Una forma fácil de evitar un gran número de pruebas (aunque no todas, naturalmente) es probar solamente con el 2, y luego solo con los impares.
Podemos ahorrar todavía más. Un número cualquiera solo será divisible por números que sean menores o iguales a su mitad. Por ejemplo, el número 40 no es divisible por ningún número entre 21 y 39. A si es que bastará con probar con el número 2, y con los números impares menores que la mitad del número a comprobar.
Esto puede mejorarse aún más. En realidad es suficiente con probar a dividir con el 2 y con todos los impares que sean menores o iguales que la raíz cuadrada del número inicial. Esto se debe a que si el número inicial, n, se puede poner como n=p·q (con p y q distintos de 1 y n). Si p y q son distintos, alguno de ellos será menor que la raíz cuadrada de n. Y si p y q son iguales, claramente serán exactamente la raíz cuadrada.
Total:
int esPrimo(n) {
if (n%2 == 0) return 1;
int c = 3;
while (c <= sqrt(n))
if (n%c == 0) return 1; else c += 2;
return 0;
}