Cómo encontrar un número primo sin usar mi función chk prime ya que deseo optimizar mis algo

long long int chkPrime(long long int z) { int i; if(z==1) return 0; if(z==2) return 1; for(i=2;i<=z/2;i++) if(!(z%i)) return 0; return 1; } 

Si desea verificar si cierto número es definitivamente primo, el algoritmo determinista más rápido (es decir, el tiempo de ejecución polinómico) es el AKS-test (Wikipedia) afaik.

Si desea crear números primos para un cierto rango, debe mirar el tamizado (Wikipedia) o, como recomendaría descargarlos como una lista de Internet (por ejemplo, aquí para los primeros 10000).

El artículo de wikipedia sobre tamizado menciona dos buenas pruebas de primalidad probabilística, por lo que no mencionaré más. Sin embargo, la prueba solo dice si un número es un número primo con una gran probabilidad (los llamados números primos probables).

Basado en mi comentario anterior, aquí hay una función más eficiente, aunque OP quería saber cómo “sin usar mi función” .

 #include #include int chkPrime(long long int z) { long long int i, rootz; if (z <= 1) return 0; if (z == 2) return 1; if (z % 2 == 0) return 0; rootz = (long long int)sqrt((double)z); for (i=3; i<=rootz; i+=2) if (z % i == 0) return 0; return 1; } int main(void) { long long int i; for (i=0; i<100; i++) if (chkPrime(i)) printf("%5lld ", i); return 0; } 

Esto es lo que puedes hacer:

 1. Determine the prime numbers upto sqrt(MaxN) using seive at the beginning of your program.(you need to calculate this only once) 2. Then each time you call chkPrime do this : -- determine sqrt(z) -- check if the number can be divided with the primes upto sqrt(z) -- if can not be divided then z is a prime number otherwise it is not. 

o, si no desea generar números primos al principio, haga lo siguiente:

  1. determine sqrt(z) 2. check if the number can be divided with 2 3. if yes then it's not a prime otherwise goto 4 4. check if the number can be divided with odd numbers from 3 to sqrt(z) 5. if yes then it's not a prime otherwise it is a prime number