#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
int es_primo(long numero);
 
int main(int argc, char** argv) {
    clock_t startTime = clock(); 
    int cantidad = 1000000;
    int encontrados = 0;
    long numero = 1;
    long primos[cantidad];
    while(encontrados < cantidad){
        numero++;
        if(es_primo(numero)){
            primos[encontrados++] = numero;
        }
    }
    clock_t endTime = clock(); 
    /*
    int i;
    for(i=0;i<cantidad; i++){
        printf("%d-",primos[i]);
    }
    */
    printf("pasaron %d millisegundos",(endTime-startTime)/1000);
 
 
    return (EXIT_SUCCESS);
}
int es_primo(long numero){
    long control_for = 0;
    if(numero <= 3) return 1;
    if(numero % 2 == 0 ||numero % 3 == 0) return 0;
    for(control_for = 5; numero > control_for * control_for; control_for+=6){
        if(numero % control_for == 0 || numero % (control_for + 2)==0) return 0;
    }
    return 1;
    }

package numerosprimos;
 
import java.util.*;
import java.lang.*;
import java.io.*;
 
public class NumerosPrimos {
 
    public static void main (String[] args){
 
        long startTime = System.currentTimeMillis();
        int cantidad = 1000000;
        int encontrados = 0;
        long numero = 1;
        long[] primos = new long[cantidad];
        while(encontrados < cantidad){
            numero++;
            if(es_primo(numero)){
                primos[encontrados++] = numero;
            }
 
        }
        long endTime = System.currentTimeMillis();
        //System.out.println(Arrays.toString(primos));
        System.out.println("pasaron: " + (endTime - startTime) + " millisegundos");
 
    }
    public static boolean es_primo(long numero){
        long control_for = 0;
        if(numero <= 3) return true;
        if(numero % 2 == 0 ||numero % 3 == 0) return false;
        for(control_for = 5; numero > control_for * control_for; control_for+=6){
            if(numero % control_for == 0 || numero % (control_for + 2)==0) return false;
        }
        return true;
    }
 
}

1,1,2,2,3,3,3,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,3,0,0,0,0,0...

import sys
import pygame
import pygame.gfxdraw
import time
pygame.init() 
 
#globales
tamano = 0 #tamano del punto, 0 = 1px, 1=3px... etc
separacion = 1 #el desplazamiento entre punto y punto, 1px
niveles = 100 #cuantas capas tendra la espiral
tiempo_maximo = 10 #si no termina de dibujar en este tiempo detiene el trabajo... switch de seguridad si tienen un pc poco potente
PRIMO = (255,255,255) #color si es primo
NO_PRIMO = (64,64,64) #color si no es primo
pantalla = {"w":niveles*2+100,"h":niveles*2+100} #tamano de la pantalla... suficiente para puntos de 1px + 100px de margen
 
window = pygame.display.set_mode((pantalla["w"], pantalla["h"]))
 
 
 
 
def dibujar():
	posicion = {"x":pantalla["w"]/2, "y":pantalla["h"]/2} #cursor en centro de pantalla
	direccion = 1 #0 derecha, 1 arriba, 2 izquierda, 3 abajo
	control = 2 #variable de control
	cantidad = 1 #cantidad de puntos dibujados
	dibCir(posicion, PRIMO) #punto central... direccion va por "referencia"
 
	inicio = time.clock() + tiempo_maximo #calcular tiempo para finalizar
	for i in range(2):#dibuja los primeros 2 puntos
		mover_dibujar(direccion, posicion, separacion, PRIMO) 
		direccion += 1
		cantidad += 1 
	puntos_totales = (niveles*2 + 1)**2 - 1 #cantidad de puntos a dibujar
 
	detener = False
 
	for mayor in range(niveles*2):
		for menor in range(2):
			for punto in range(control):
				if esPrimo(cantidad): #color a dibujar
					mover_dibujar(direccion, posicion, separacion, PRIMO)
				else:
					mover_dibujar(direccion, posicion, separacion)
 
				if time.clock() > inicio: detener=True #si se pasa del tiempo
				if (cantidad == puntos_totales): detener=True #si se dibujaron los puntos necesarios
				cantidad +=1
				if(detener): break
			direccion = (direccion+1)%4 #cambia la direccion del recorrido
			if(detener): break
		control += 1
		if(detener): break 
		pygame.display.flip() #dibuja la capa calculada
	print cantidad #imprime los puntos dibujados en la consola
	return 0
 
 
def mover_dibujar(direccion, posicion, separacion, color=NO_PRIMO): #dirije el recorrido y dibuja
	if direccion == 0: posicion["x"] -= separacion
	if direccion == 1: posicion["y"] += separacion
	if direccion == 2: posicion["x"] += separacion
	if direccion == 3: posicion["y"] -= separacion
	dibCir(posicion, color)
 
def dibCir(posicion, color ,r=tamano): 
	pygame.gfxdraw.filled_circle(window, posicion["x"],posicion["y"], r, color) #dibuja el circulo 
	#pygame.gfxdraw.aacircle(window, posicion["x"],posicion["y"], r, color) #lo suaviza mas
 
 
def esPrimo(n): #calcula si es primo
   if n <= 3:
       return n >= 2
   if n % 2 == 0 or n % 3 == 0:       return False
   for i in range(5, int(n ** 0.5) + 1, 6):
       if n % i == 0 or n % (i + 2) == 0:
           return False
   return True
 
 
 
dibujar() #ejecuta todo
 
 
#input handling (somewhat boilerplate code):
 
while True:  #copypaste para mentener abierta la ventana
   time.sleep( 1 ) #sin esto se consume todos los recursos
   for event in pygame.event.get(): 
      if event.type == pygame.QUIT: 
          sys.exit(0)
      #else: 
      #   print event 
 
 

(d*e)%phi == 1

def bidimArray(a,b): #crear array bidimensional
	return [[0 for x in range(b)] for x in range(a)] 
 
def esPrimo(n): #calcula si es primo
    if n <= 3:
        return n >= 2
    if n % 2 == 0 or n % 3 == 0:
        return False
    for i in range(5, int(n ** 0.5) + 1, 6):
        if n % i == 0 or n % (i + 2) == 0:
            return False
    return True
 
def nvoPrimo(n): # conseguir el n-avo primo
	total = 0
	contador = 1
	while total < n:
		contador+=1
		if esPrimo(contador):
			total+=1
	return contador
 
global_factores = [] #buffer de factores
 
def obtenerFactores(numero): #obtiene los factores de un numero dado
	for i in global_factores: #si esta en buffer los saca de ahi
		if i[0] == numero:
			return i[1]
	factores = []
	buff = 1
	while buff/2 < numero:
		buff+=1
		if numero % buff == 0:
			factores.append(buff)
	#print global_factores #debug
	global_factores.append([numero,factores]) #los mete en el buffer
	return factores
 
def esCoprimo(a,b): #son coprimos?
	f_a = obtenerFactores(a)
	f_b = obtenerFactores(b)
	comunes = len(frozenset(f_a).intersection(f_b)) #intercepta
	#print comunes #debug
	if comunes > 0: return False #si hay coincidencia, no son coprimos
	return True
 
def calcular_e(phi,n, inicio):
	buff = 0 + inicio
	e = 0
	if buff < 1: buff = 1
	while buff < phi:
		buff+=1
		#print "{} y {}".format(buff, n) #debug
		if esCoprimo(buff, n) and esCoprimo(buff, phi) : 
			e = buff
			break
	return e
 
 
def calcular_d(e,phi,n):
	d = 0
	buff = 0
	for contador in range(n):
		buff = (contador * e)%phi
		#print "({} * {})%{} -> {}".format(contador,e,phi,buff) #debug
		if buff == 1:
			d = contador
			break
	return d
 
def cifrado(m,e,n):
	return pow(m,e,n) # m^e%n
 
def descifrado(c,d,n):
	return pow(c,d,n) # c^d%n
 
def aplicarRSA(p,q,m):
	if not esPrimo(p):
		print "p debe ser primo"
		exit()
 
	if not esPrimo(q):
		print "q debe ser primo"
		exit()
 
 
	n = p * q
	if m >= n:
		print "mensaje muy grande, p y q deben ser mayores"
		print "maximo mensaje permitido {}".format(n-1)
		exit()
	phi = (p-1)*(q-1)
	e = calcular_e(phi,n,0)
	d = calcular_d(e,phi,n)
	c = 0
	print "p = {} y q = {}".format(p,q)
	print "n = {} y phi(n) = {}".format(n,phi)
	print "Llave publica es ({},{})".format(e,n)
	print "Llave privada es ({},{})".format(d,n)
	c = cifrado(m,e,n)
	print "cifrado de {} resulta {}".format(m,c)
	m = descifrado(c,d,n)
	print "descifrado de {} resulta {}".format(c,m)
 
aplicarRSA(nvoPrimo(20),nvoPrimo(32),100)

bidimArray(a,b)

esPrimo(n)

nvoPrimo(n)

obtenerFactores(numero)

esCoprimo(a,b)

aplicarRSA(nvoPrimo(20),nvoPrimo(32),100)

from random import randint #yeap vamos a generar int random
 
def colocarPremio():
  puertas = [0,0,0] #establecemos 3 puertas
  puertas[randint(0,2)] = 1 #colocamos premio en una
  return puertas
 
def seleccionJugador():
  return randint(0,2) #el jugador escoge una puerta
 
def mostrarPuerta(jugador, puertas):
  presentador = 0 #el presentador entra y saluda a todos
  for i in range(3):
    if puertas[i] == 0 and not i == jugador: #el presentador escoge una puerta que no sea la del jugador y no tenga premio
      presentador = i #y se queda con esa puerta
      break #porque no tiene que seguir buscando
  return presentador
 
def cambiarPuerta(presentador, jugador):
  for i in range(3):
    if not i == presentador and not i == jugador: #el jugador escoge la otra puerta cerrada
      jugador = i #y se queda con esa
      break #porque no tiene que seguir buscando
  return jugador
 
def juego(cambiar):
  puertas = colocarPremio() #ponemos las puertas y el premio
  jugador = seleccionJugador() #el jugador escoge
  presentador = mostrarPuerta(jugador, puertas) #el presentador muestra
  if cambiar: jugador = cambiarPuerta(presentador, jugador) #debo cambiar?
  return puertas[jugador] #tendra premio?
 
 
jugadas = 100 #cuantas veces te lo tengo que repetir para convencerte?
cambio = True #cambiar o no cambiar, he alli el dilema
 
contador = 0 #contador victorias
for i in range(jugadas): contador += juego(cambio) #el momento de la verdad... juguemos
 
if not cambio: cambio = 'no ' #formateo cadena bonita
else:  cambio = '' #y por si...
 
print 'en {} jugadas hubo {} victorias si el jugador {}cambiaba de puerta'.format(jugadas,contador,cambio) #resultado