C Ejemplo de práctica 33 - Determinación de números primos

C 语言经典100例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 0

C 语言经典100例100 ejemplos clásicos del lenguaje C

Otras extensiones