Cómo escribir un programa C para verificar si un número es primo o no

Answer 1

Dos personas respondieron la pregunta y ambas son una solución demasiado ingenua.

Hay muchos algoritmos disponibles para pruebas principales.
1. Pequeño teorema de Fermat.
2. Pruebas Miller Rabin.
y muchos más.
Aquí Miller Rabin está disponible en varios idiomas.
Prueba de primalidad de Miller-Rabin

Aquí explicaré a Miller Rabin.
Prueba de primalidad de Miller-Rabin
Ideas y conceptos clave

1. Según el pequeño teorema de Fermat, si p es un número primo y a es un número entero positivo menor que p, entonces
   a ^ p = a (mod p) o alternativamente: a ^ (p-1) = 1 (mod p)
2. Si p es primo y x ^ 2 = 1 (mod p), entonces x = +1 o -1 (mod p). Podríamos probar esto de la siguiente manera: x ^ 2 = 1 (mod p) x ^ 2 – 1 = 0 (mod p)
3. (x-1) (x + 1) = 0 (mod p)

Ahora bien, si p no divide tanto (x-1) como (x + 1) y divide su producto, entonces no puede ser un primo, lo cual es una contradicción. Por lo tanto, p dividirá (x-1) o dividirá (x + 1), entonces x = +1 o -1 (mod p).
Supongamos que p – 1 = 2d * s donde s es impar yd> = 0. Si p es primo, entonces, ya sea como = 1 (mod p) como en este caso, la cuadratura repetida de como siempre producirá 1, entonces (a (p-1))% p será 1; o a (s * (2r)) = -1 (mod p) para alguna r tal que 0 <= r <d, ya que la cuadratura repetida siempre dará 1 y finalmente a (p-1) = 1 (mod p ) Si ninguno de estos es cierto, a (p-1) no será 1 para ningún número primo a (de lo contrario, habrá una contradicción con el hecho # 2).
La complejidad es el número de O (iteraciones * log n);

y este algoritmo funcionará para grandes números 10 ^ 18.

Espero que esto ayude.

#include #include long long mul(long long a,long long b,long long c); long long mod(long long a,long long b,long long c){ long long x=1,y=a; while(b > 0){ if(b%2 == 1){ x=mul(x,y,c); } y = mul(y,y,c); b /= 2; } return x%c; } long long mul(long long a,long long b,long long c){ long long x = 0,y=a%c; while(b > 0){ if(b%2 == 1){ x = (x+y)%c; } y = (y*2)%c; b /= 2; } return x%c; } int Miller(long long p,long long it){ if(p<2){ return 0; } if(p!=2 && p%2==0){ return 0; } long long s=p-1; while(s%2==0){ s/=2; } long long i; for(i=0;i<it;i++){ long long a=rand()%(p-1)+1,tt=s; long long md=mod(a,tt,p); while(tt!=p-1 && md!=1 && md!=p-1){ md=mul(md,md,p); tt *= 2; } if(md!=p-1 && tt%2==0){ return 0; } } return 1; } int main() { long long test , n; scanf("%lld" , &n); int fl = Miller(n , 20); if(fl) printf("YES number is Prime\n"); else printf("NO Number is not Prime\n"); return 0; } 

Answer 2

Esta lógica es de una sola línea y funciona para n> 1

int main ()

{

int n, i;

scanf (“% d”, & n);

i = n / 2;

mientras que (n% i–);

if (i) printf (“No cebado”);

sino printf (“Prime”);

devuelve 0;

}

créditos: #PSR señor, #KVK señor

#HAPPY_CODING 🙂

Answer 3

Voy directamente al código.

#include

int main ()

{

int n, i;

printf (“\ nEntrar n”);

scanf (“% d”, & n);

para (i = 2; i <= n-1; i ++)

{

si (n% i == 0)
{

printf (“n no es primo”);

rotura;

}

}

si (n == i)

{

printf (“n es primo”);

}

devuelve 0;

}

Espero que este problema esté en el libro LET US C como ejemplo de declaración de ruptura.

Puede hacer esto usando “flag”, también usando i <= n / 2 o puede verificar el valor de i hasta n ^ (1/2). Estos generalmente se usan en la codificación competitiva.

Disfruta codificando.

Answer 4

#include

#include

vacío principal

{

int i, n, c = 0;

para (i = 1; i <= n; i ++)

{

si (n% i == 0)

{

c ++;

}

}

si (c == 2)

{

printf (“el número es primo”);

}

más

{

printf (“el número no es primo”);

}

}

// instagram- rahulparth

Answer 5

Primera solución (Todo el cálculo realizado dentro de main() ):

  #include 

 #include 

 int main ()

 {

     int n;

     int i;

     int isComposite = 0;

     scanf ("% d", & n);

     para (i = 2; i <= (int) sqrt ((double) n); i ++) {

         if (n% i == 0) {

             printf ("el número es compuesto");

             isComposite = 1;

             rotura;

         }

     }

     if (! isComposite) {

         printf ("el número es primo");

     }

     devuelve 0;



 }

Segunda solución (Cálculo realizado en un método separado, solución más legible):

  #include 

 #include 



 int prime (int a)

 {

     int b = 2, n = 0;



     para (b = 2; b 
    

Answer 6

No te voy a dar el código directamente ya que parece ser un principiante y debería probarlo, pero ¿qué tal una pista:

Tome un número. Toma una variable de conteo. Si el número es divisible por cualquier número entre 1 y sí mismo (ambos incluidos) , el recuento aumenta en uno.

Si el recuento es 2 , es decir, el número es divisible por solo 2 números (que obligatoriamente será 1 y sí mismo ), o en otras palabras, tiene solo 2 factores (1 y en sí mismo) es primo .

De lo contrario , es decir, si tiene más factores que 2, es compuesto .

Otra forma de determinar es que si el recuento es cero cuando excluye 1 y el número mientras verifica la divisibilidad. Significa, si el número no tiene (o cero) factores excluyendo 1 y sí mismo.

Necesitará un bucle para ambos casos.

Ahora intenta expresar la lógica como el código. ¡La mejor de las suertes!

Espero que haya ayudado. Pregúntame de nuevo si necesitas más ayuda.

Answer 7

La respuesta a este problema según lo declarado por Lakshmann Tiwari es correcta y quiero agregar otra forma de calcular números primos, tamiz de eratóstenes

En este método marcamos, múltiplo de todos los números primos como no primos , y luego buscamos en la matriz dicho número.

Desventaja: se puede usar para calcular números primos solo hasta 10 ^ 7

  #include 
 usando el espacio de nombres estándar;
 #define MAX 10000010
 int prime [MAX];
 tamiz vacío () {
	 memset (prime, 0, sizeof (prime));
	 para (int i = 2; i > n;
	 tamiz();
	 prime [n] == 0? cout << "SÍ" << endl: cout << "NO" << endl;
	 devuelve 0;
 }

Enlace de Ideone : Ideone.com

Answer 8

#include

#include

int main ()

{

int n, i, j = 0;

printf (“ingrese el no”);

scanf (“% d”, & n);

para (i = 2; i

{

si (n% i == 0)

{

rotura;

}

más{

Hacer continuación;

}

}

si (i == n)

{

printf (“primo”);

}

más{

printf (“no es un primo”);

}

devuelve 0;

}

Answer 9

Tengo un código C que se puede usar para encontrar si algún número es primo o no. Espero que esto sea lo suficientemente eficiente y fácil para que nadie lo entienda

  #include 
 #include 
 int prime (int num)
 {
	 int i;
	 para (i = 2; i 
  Aquí estoy ejecutando el ciclo desde 2 hasta la raíz cuadrada del número dado para reducir el número de iteraciones.  Y el ciclo se cierra tan pronto como encuentra cualquier factor de un número dado mayor que 1. Esto es para obtener la máxima eficiencia del código. 
  Vota a favor si te resulta útil 🙂 

    

Answer 10

Paso 1: comenzar

Paso 2: obtén los números dados

Paso 3: verifique si el número tiene algún divisor que no sea 1 y el número mismo

Paso 4: si hay un divisor que no sea 1 o ese número en sí, entonces

Paso 5: considere el número como NO PRIME

Paso 6: de lo contrario, considere el número como un PRIMER NUMBER

Paso 7: muestra el resultado

Paso 8: Fin

Answer 11

Aquí he pegado el código para ver si te ayuda.

Answer 12

Tienes que usar el método de recursión