C Ejemplo de práctica 33 - Determinación de números primos
100 ejemplos clásicos del lenguaje C
Problema:Determinar si un número es primo.
Análisis del programa:Los números primos (prime number), también llamados números primos, son infinitos. Un número natural mayor que 1, aparte de 1 y de sí mismo, no puede ser divisible por otros números naturales.
Código fuente del programa:
Ejemplo
#include<stdio.h>
#include<math.h>
#define MAX 1000 // Tamaño máximo del arreglo
int prime[MAX]; // Arreglo que almacena si es número primo
// Método simple para determinar si un número es primo (fuerza bruta)
int isPrimeNaive(int n)
{
if (n <= 1) // Los números menores o iguales a 1 no son primos
return 0;
for (int i = 2; i < n; i++) // Verificar uno por uno desde 2 hasta n-1 si pueden dividir a n
if (n % i == 0) // Si puede dividir exactamente, entonces no es primo
return 0;
return 1; // Si no se encuentra ningún factor, entonces es primo
}
// Método optimizado para determinar números primos: solo verificar hasta sqrt(n) y omitir los pares
int isPrime(int n)
{
if (n <= 1) // Los números menores o iguales a 1 no son primos
return 0;
if (n == 2) // 2 es primo
return 1;
if (n % 2 == 0) // Excluir números pares
return 0;
int limit = (int)sqrt((double)n); // Solo es necesario verificar hasta sqrt(n)
for (int i = 3; i <= limit; i += 2) // Comenzar desde 3, verificar solo números impares
{
if (n % i == 0) // Si puede dividir exactamente, entonces no es primo
return 0;
}
return 1; // Si pasa todas las pruebas, n es primo
}
// Inicializar la tabla de primos con el método de la criba
void sieve()
{
for (int i = 0; i < MAX; i++)
prime[i] = 1; // Suponer que todos los números son primos
prime[0] = prime[1] = 0; // 0 y 1 no son primos
int limit = (int)sqrt((double)MAX); // Solo es necesario verificar hasta sqrt(MAX)
for (int i = 2; i <= limit; i++) // Comenzar desde 2, recorrer cada número
{
if (prime[i]) // Si i es primo
{
for (int j = i * i; j < MAX; j += i) // Marcar los múltiplos de i como no primos
prime[j] = 0;
}
}
}
// Determinar si un número es primo mediante el método de la criba
int isPrimeSieve(int n)
{
return prime[n]; // Devolver directamente si la posición es un número primo
}
int main()
{
sieve(); // Inicializar el cribado de números primos
// Probar si varios números son primos
printf("N=%d %d\n", 1, isPrime(1)); // Salida: 1 no es primo
printf("N=%d %d\n", 2, isPrime(2)); // Salida: 2 es primo
printf("N=%d %d\n", 3, isPrime(3)); // Salida: 3 es primo
printf("N=%d %d\n", 4, isPrime(4)); // Salida: 4 no es primo
printf("N=%d %d\n", 7, isPrime(7)); // Salida: 7 es primo
printf("N=%d %d\n", 9, isPrime(9)); // Salida: 9 no es primo
printf("N=%d %d\n", 13, isPrime(13)); // Salida: 13 es primo
printf("N=%d %d\n", 17, isPrime(17)); // Salida: 17 es primo
printf("N=%d %d\n", 100, isPrime(100)); // Salida: 100 no es primo
printf("N=%d %d\n", 23, isPrime(23)); // Salida: 23 es primo
printf("N=%d %d\n", 1, isPrime(1)); // Salida: 1 no es primo
return 0;
}
El resultado de salida del ejemplo anterior es (el dígito final 1 indica que es primo, 0 indica que no es primo):
N=1 0 N=2 1 N=3 1 N=4 0 N=7 1 N=9 0 N=13 1 N=17 1 N=100 0 N=23 1 N=1 0Otras extensiones