Buscar

sábado, 21 de enero de 2012

Algoritmo para saber si un numero es primo

Numero primo:

N=numero a comprobar si es primo ;
C=numero que aumenta e ira dividiendo a N;
D=cantidad de divisores del numero; 

El símbolo "%" que se muestra en la imagen en algoritmos significa "mod" que se encarga de sacar el resto de una división. 

La lógica de este algoritmo es leer un numero N validar que sea mayor que cero ya que no existe numero primo menor que 1; luego ir dividiendo el numero N entre el contador C que ira aumentando de uno en uno según lo indica el ejercicio de la imagen; luego si el; N% C=0; el contador de divisores D aumentara de uno en uno; para finalizar se comparara si la variable D es igual a 2, si es igual a 2 es primo ya que los números primos solo tienen 2 divisores.

CLICK PARA VISUALIZAR MEJOR LA IMAGEN

15 comentarios:

  1. function b = numero_primo(n)

    b=%t
    if n==1
    b=%f
    else
    for i=2:floor ( sqrt(n))
    if modulo (n,i)==0
    b=%f
    break
    end
    end
    end
    endfunction

    ResponderEliminar
    Respuestas
    1. Que lenguaje de programación es ese?
      If es c++ con que librería iciste ese código?

      Eliminar
    2. Que lenguaje de programación es ese?
      If es c++ con que librería iciste ese código?

      Eliminar
    3. Este comentario ha sido eliminado por el autor.

      Eliminar
  2. Este algoritmo es correcto, pero no es de lo más eficiente, ya que realiza procesos innecesarios.

    Un número natural mayor que 1 puede o bien ser primo (si tiene dos divisores), o ser compuesto (si tiene más de dos divisores).

    Realmente no es necesario calcular el número de divisores que tiene un número natural N para saber si es primo o compuesto. Con tan solo saber si dicho número natural N es divisible entre un número mayor que 1 y menor que √N sabremos que es compuesto, de lo contrario, es primo.

    Claro que si √N es exacta, entonces significa N es compuesto.

    Pero podemos simplificar esto aún más, ya que si un número mayor que 2 es par, entonces es compuesto; por otro lado, un número impar, nunca será divisible entre un número par.

    Resumiendo todo, tenemos que:
    - Si √N es exacta, entonces N es compuesto.
    - Un número par mayor que 2 es compuesto.
    - Un número impar N es compuesto si es divisible entre un número impar mayor o igual que 3 y menor que √N.

    Entonces, el algoritmo sería el siguiente:
    1. Leer N.
    2. Si N = 0, N no es primo; si N = 1, N no es primo; si N = 2, N es primo. En caso de que ninguna de estas situaciones se cumpla, sigamos al paso 3.
    3. Si N mod 2 = 0, entonces N no es primo. De lo contrario seguimos al paso 4.
    4. Llamamos M a la raíz cuadrada de N (M = √N), si la raíz es exacta, entonces N no es primo. De lo contrario, seguimos al paso 4.
    5. Hacemos C = 3, y mientras C ≤ M si N mod C = 0, entonces N no es primo, de lo contrario, incrementamos dos unidades a C. Si C > M, entonces N es primo.

    ResponderEliminar

Síguenos en Facebook