Derterminar si un numero es Primo
Como se podria crear una lista con todos los primos absolutos desde 1 hasta un numero en cuestion?
Bienvenido al mundo de los numeros primos, la respuesta te la estas dando tu mismo.
Primero necesitas determinar los numero Primos que existen desde 2 hasta el numero en cuestion.
Una vez definida esa lista necesitas procesar los digitos de cada uno de esos numeros y detenerminar si suma es un numero primo hasta llegar a un solo digito.
Por lo cual tu primer problema es detenerminar si un numero es primo o no.
Metodos para lo mismo hay muchos, desde exhaustivos, probabilisticos.
Lo ideal para estar 100% seguro de que es primo o no, es ir contruyendo una lista de numeros primos, y probar todos los numero siguientes contra esa lista. Por ejemplo emepzamos con el 2, primer numero primo.
Luego 3, ¿es tres divisible entre 2? en otras palabras ¿ 3 modulo 2 es 0 ? Si la respuesta a esta ultma es negativa podemos agregar 3 a nuestra lista de numeros primos.
Luego 4, ¿Es cuatro divisible entre 2? si 4 % 2 es 0, entonces 4 No es numero primo.
Luego 5 es cinco divisible entre 2, como 5%2 no es 0, y como 5 % 3 no es 0, entonces agregamos 5 a nuestra lista de numeros primos.
Asi sucedivamnete hasta el numero N, entonces ya con la lista definida de numeros primos, procedes a simplificar la suma de sus digiitos como mencionaste hasta llegar a un numero de un solo digito, con lo cual tienes tu problema resulto.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
unsigned int *primos = NULL;
int n_primos = 0;
int agregar_numero(unsigned int numero);
int es_primo(unsigned int numero);
int es_primo_absoluto(unsigned int numero);
int main() {
unsigned int i,j;
unsigned int N = 0xFFFFFF;
agregar_numero(2);
printf("El numero %i es primo y ademas es Primo Absoluto\n",2); i = 3;
while(i < N) {
j = 0;
if(es_primo(i)) {
printf("El numero %i es primo\n",i
); agregar_numero(i);
if(es_primo_absoluto(i)){
printf("El numero %i es primo y ademas es Primo Absoluto\n",i
); }
}
i+=2; //Vamos de 2 en 2 por que no necesitamos evaluar los numeros pares, es decir solo 3, 5, 7, 9 .... Asi evistamos llamdas inecesarias a la funcion es_primo, haciendo nuestro programa un tanto mas eficiente
}
return 0;
}
int agregar_numero(unsigned int numero) {
primos
= realloc(primos
,sizeof(int) * (n_primos
+1)); primos[n_primos] = numero;
n_primos++;
}
int es_primo(unsigned int numero) { //Esta funcion solo determina correctamente si es primo o no, cuando ya hemos EVALUADO todos los numeros PREVIOS a este numero
int es_primo = 1;
int j = 0;
while(j < n_primos && primos[j] < (numero/2) && es_primo) {
es_primo = (numero % primos[j++] == 0) ? 0 : 1 ;
}
return es_primo;
}
int es_primo_absoluto(unsigned int numero) {
int retornar;
char temporal[20] = {0};
unsigned suma = 0;
int len,i;
if(len == 1) {
switch(numero) {
case 2:
case 3:
case 5:
case 7:
retornar = 1;
break;
default:
retornar = 0;
break;
}
}
else {
i = 0;
while(i < len) {
suma = temporal[i++] - '0';
}
if(es_primo(suma)) {
retornar = es_primo_absoluto(suma);
}
else {
retornar = 0;
}
}
return retornar;
}
Saludos
Autor
En línea
