C/Visual C - Numeros primos en Turbo C++

Necesito un programa que me ayude a determinar si un numero es primo o no, preferiblemente en pseudo-codigo o en C++.

Hola

Este ejemplo te servirá:

#include <iostream.h> //cout, cin

void main()
{
int N,k;

cout<<"Ingrese un número: ";
cin>>N;

cout<<"\nEl número ";

for( k=2; N%k; k++); // N será un primo, si solo es divisible por N
// o por la unidad.
if( N==k )
cout<<"SI"; // N si es número primo
else
cout<<"NO"; // N no es número primo

cout<<" es primo.";

}

Suerte.

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;
}