Project euler problema 1 (A papel y lapiz)

Estaba revisando un libro sobre sumatorias y recordé este problema de PE( projecteuler.net/problem=1 ): hay que sumar los números menores a 1000 que son múltiplos de 3 o de 5.

El problema es muy simple si sabes algún lenguaje de programación y lo básico(estructuras de repeticion y de selección) entonces será sencillo. Una forma posible diferente a la común es (en python):

sum(range(3,1000,3)) + sum(range(5,1000,5)) - sum(range(15,1000,15))

Lo que hace es sumar todos los múltiplos de 3, luego los de 5 y restarle los de 15, ya que cuando hizo los de 3 (3,6,9,12,15...)y los de 5(5,10,15...) contó dos veces los múltiplos de 15.

Bueno pero esta forma es muy común y muy simple, así que la abordé desde el punto de vista de las sumatorias, primero algo básico:

La sumatoria de los n primeros enteros positivos(1+2+...n) es: n*(n+1)/2

En este problema queremos sumar los múltiplos de 3 menores a 1000. Los múltiplos de 3 los podemos expresar mediante: 3*i. De la misma forma expresaremos los múltiplos de 5( 5*i)

Ahora si son los múltiplos menores a 1000, pues será la suma desde 1, hasta [999/3] de 3*i (donde [ ] es la parte entera) y lo mismo con los múltiplos de 5. Luego le restaremos los múltiplos de 15 y tendremos la respuesta. Con la fórmula anterior tendríamos que(la constante se puede escribir por fuera de la sumatoria):

3*(n*(n+1)/2) = 3*(333*334/2)
Igual para 5 y 15, y luego los sumamos(restamos la de 15 por lo que se dijo antes):

Solución = (3×333×334÷2)+ (5×199×200÷2) − (15×66×67÷2)

De esta forma obtenemos la solución para el primer problema de PE de una forma bastante rápida(Si es que no es la más rápida y sencilla una vez que sabemos cómo abordarlo con sumatorias). Si tienes alguna solución diferente, coméntala!

Test de primalidad

Cómo saber si un número es primo? Muchas veces necesitamos crear un algoritmo para saber si un número es primo o no. Pues bien, no se trata de una tarea muy difícil, si están participando en alguna competencia, seguro les servirá alguno de los siguientes algoritmos.

Un número es primo si sólo es divisible por él mismo y la unidad. Por definición el uno no es primo.

2,3,5,7,11,13,17,19,23,29...

Si queremos escribir el código para saber si un número es primo tendríamos que iterar desde 1 hasta el número y preguntar y esos números dividen a n. Si al final sólo 2 lo dividen, entonces el número es primo. (Un número i divide a n si el residuo de la división es 0, es decir si la división es exacta, si el % es 0)

cont = 0;
for(int i=1;i<=n;i++)
    if (n%i==0)
        cont+=1;
if(cont==2)
    System.out.println("Primo");
else
    System.out.println("No es primo");

o podriamos iterar desde 2 hasta uno antes que n y si algun numero divide a n, estos serian diferentes a 1 y a n, entonces no es primo:

boolean primo = true;
for(int i=2;i<n;i++)
    if (n%i==0){
        primo = false;
        break;
    }
if(primo)
    System.out.println("Primo");
else
    System.out.println("No es primo");

Estas son las formas que se nos ocurren a todos, y es fácil de pensar pero no es muy eficiente, ya que si pusiéramos un número un poco más grande...o mejor aún varios números tardaría bastante. Una pequeña mejor que le podemos hacer es sólo iterar hasta la mitad del número(incluyéndolo) ya que un número no tiene divisores más allá de su mitad. Pero algo aún mejor es sólo iterar hasta la raiz cuadrada del número ya que si dividimos un número por un número más grande que su raíz cuadrada el cociente será un número menor a su raíz. Por ejemplo:

16/8=4

Lo que es igual a la raíz cuadrada.

Mucho más simple si tan pronto encontramos un divisor decimos que n no es primo:(además si descartamos si es par, ya sabemos que no es primo o si es uno y luego sólo iteramos a través de los impares):

if((n&1)==0 && n!=2) || n==1) return false;//si es par y es diferente de 2 porque el 2 es primo
for(int i=3;i<=Math.sqrt(n);i+=2)
    if(n%i==0)
        return false;
return true;

Existen otras formas más complicadas pero más eficientes de saber si un número es primo, para complementar me gustaría compartir una regex que encontré por ahí para verificar si un número es primo en binario:

http://stackoverflow.com/questions/2795065/how-to-determine-if-a-number-is-a-prime-with-regex