elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Introducción a la Factorización De Semiprimos (RSA)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Numeros primos n/2 Limite superior
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Numeros primos n/2 Limite superior  (Leído 1,784 veces)
Raiden

Desconectado Desconectado

Mensajes: 25



Ver Perfil
Numeros primos n/2 Limite superior
« en: 23 Agosto 2021, 14:21 pm »

Hola a todos,
Eh estado haciendo unos ejercicios sobre funciones y me encontre con una consigna que no logre entenderla.
Dice  "Al principio podria pensarse que n/2 es el limite superior para evaluar si un numero es primo. pero lo máximo que se necesita es ir hasta la raíz cuadrada de n, Por que?"
Lo de la raiz pude entenderlo pero sobre lo de n/2 ¿como se llega a relacionar con los numeros primos y c++? ya he buscado por internet pero no encuentro nada.

Gracias por cualquier aporte.  ::)
Saludos.


En línea

MAFUS


Desconectado Desconectado

Mensajes: 1.575



Ver Perfil
Re: Numeros primos n/2 Limite superior
« Respuesta #1 en: 23 Agosto 2021, 18:57 pm »

n es el número al que se buscan los primos.
\frac{n}{\frac{n}{2}} = 2
y 2 es el primer primo. Así
\frac{n}{\frac{n}{2}+1} < 2
Por lo que cualquier número por encima de
\frac{n}{2}
salvo n, no dará un número entero y por tanto no es divisible.


« Última modificación: 23 Agosto 2021, 19:00 pm por MAFUS » En línea

K-YreX
Moderador
***
Desconectado Desconectado

Mensajes: 1.001



Ver Perfil
Re: Numeros primos n/2 Limite superior
« Respuesta #2 en: 23 Agosto 2021, 19:03 pm »

Realmente si no eres capaz de relacionarlo se podría decir que vas bien pues en caso de encontrar tal relación, estarías equivocado.

Todo esto viene a raíz de (no lo hice a propósito  :rolleyes:) del siguiente ejercicio típico o cualquiera de sus variantes:
Citar
Crea un programa que, dado un número entero positivo n, determine si es o no primo.
Como tú y yo sabemos, un número primo es aquel que solo se puede dividir por uno mismo y la unidad (1), por ejemplo: 2, 3, 5, 7... (el 1 en la mayoría de casos no es considerado como un número primo pero eso da para otro tema por lo que lo dejaremos ahí)

La solución más básica y menos eficiente (llamémosla: el cerdito que hizo la casa de paja) sería calcular todos los divisores de n y ver si son 2 o más:
Código:
divisores := 0
PARA i := 1 HASTA n HACER
  SI n % i == 0 ENTONCES
    divisores := divisores + 1
  FIN SI
FIN PARA

SI divisores == 2 ENTONCES
  El numero n SI es primo
SINO
  El numero n NO es primo
FIN SI

Pero un día el hermano del anterior (el cerdito que hizo la casa de madera) dijo:
Citar
Si ya tenemos más de 2 divisores, para qué vamos a seguir comprobando?
y creó algo mejor:
Código:
i := 1
divisores := 0
MIENTRAS i <= n && divisores <= 2 HACER
  SI n % i == 0 ENTONCES
    divisores := divisores + 1
  FIN SI
  i := i + 1
FIN MIENTRAS

SI divisores == 2 ENTONCES
  El numero n SI es primo
SINO
  El numero n NO es primo
FIN SI

Pero entonces el mayor de los 3 (el cerdito que hizo la casa de piedra), que era bueno en matemáticas porque era arquitecto por lo menos, dijo:
Citar
- Un número primo es aquel que únicamente puede expresarse como producto de 2 números naturales: n = a * b donde a = 1 y b = n o a la inversa (por la propiedad conmutativa del producto).
- Siempre 1 <= a, b <= n (a y b estarán en el rango [1,n]).
- Todo coeficiente a tendrá un coeficiente complementario b que se calcula como: b = n / a.
Entonces: Existe un punto medio x que cumple: (1 <= a <= x) y (x <= b <= n) teniendo como premisa a <= b (sin darles la vuelta a a y b). Lo que significa que solo hay que buscar algún valor que cumpla las condiciones de a para saber que existirá un b. Por lo que solo habrá que buscar en el rango [1, x] y no en el rango [1, n].
Entonces: Como a y b siempre están en el rango [1, n], el punto medio es x = n/2.
y diseñó lo que parecía la mejor solución de todas:
Código:
i := 1
divisores := 0
MIENTRAS i <= n/2 && divisores <= 2 HACER
  SI n % i == 0 ENTONCES
    divisores := divisores + 1
  FIN SI
  i := i + 1
FIN MIENTRAS

SI divisores == 1 ENTONCES // 1 porque no vamos a llegar hasta n que también es divisor
  El numero n SI es primo
SINO
  El numero n NO es primo
FIN SI

Los dos cerditos menores quedaron asombrados y fueron los 3 juntos a comercializar "el mejor algoritmo del mundo para encontrar números primos". Pero justo cuando iban a conseguir el reconocimiento mundial, apareció el lobo que era todavía mejor en matemáticas que el cerdito arquitecto y dijo:
Citar
Con todo lo anterior, el valor más grande de a es aquel que cumple que a = x. En tal caso, b tiene que valer su valor más pequeño que también es x.
Entonces: n = a * b se podría expresar como n = x * x. Un número x que multiplicado por si mismo da n, y esto hace referencia a la definición de raíz cuadrada de n.
Entonces: x no es n/2. x = sqrt(n). sqrt significa raíz cuadrada: square root.
Con esto el lobo mejoró el algoritmo del cerdito mayor y dejó a los 3 hermanos sin su ansiada recompensa.
Código:
i := 1
divisores := 0
MIENTRAS i <= sqrt(n) && divisores <= 1 HACER
  SI n % i == 0 ENTONCES
    divisores := divisores + 1
  FIN SI
  i := i + 1
FIN MIENTRAS

SI divisores == 2 ENTONCES
  El numero n SI es primo
SINO
  El numero n NO es primo
FIN SI

Todos estos códigos pueden ser implementados en muchos lenguajes de programación, entre ellos C++.
Así es como C++, los números primos, n/2, sqrt(n) y la fábula de los 3 cerditos están todos relacionados entre sí.
En línea

Código
  1. cout << "Todos tenemos un defecto, un error en nuestro código" << endl;
Raiden

Desconectado Desconectado

Mensajes: 25



Ver Perfil
Re: Numeros primos n/2 Limite superior
« Respuesta #3 en: 24 Agosto 2021, 14:42 pm »

Gracias por responder, me ayudo bastante a entender la cuestion:

Saludos hasta la proxima.  :D

En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
[Python 2.6] Funcion generadora de Numeros primos (5.761.455 primos en 19 seg)
Scripting
katas 2 8,831 Último mensaje 10 Marzo 2010, 01:50 am
por Novlucker
NUMEROS PRIMOS
Programación C/C++
ALONSOQ 5 2,682 Último mensaje 16 Junio 2012, 18:13 pm
por ALONSOQ
Numeros primos
Programación C/C++
Ander123 6 2,293 Último mensaje 30 Agosto 2012, 21:15 pm
por leosansan
Numeros Primos
Programación General
AlbertoBSD 5 1,787 Último mensaje 19 Mayo 2016, 14:21 pm
por kub0x
numeros primos
Programación C/C++
wicd 3 2,022 Último mensaje 2 Julio 2017, 03:54 am
por wicd
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines