Numeros primos - Página 2

roguer · 04-Dec-2008, 20:37

Oigan aun puedo entrar a competir????
igual ahi les va mi codigo

//////////////////Created by Roguer////////////////////////
#include<iostream>
#include<stdlib.h>
using namespace std;

int main()
{
int numero=3;
int limite;
bool primo=true;
cout<<"1,2,";
while(numero<20000)
{
limite=numero/2;
primo=true;
for(int i=3;i<limite;i+=2)
{
if(numero%i==0)
{
primo=false;
}
}
if(primo)
{
cout<<numero<<",";
}
numero+=2;
}
cout<<endl;
system("pause");
return 0;
}
///////////////////////////fin//////////////////////////////////

Espero les guste es bastante rapido
y ojala no tenga errores en la logica, si detectan algo me avisan
jejejeje

phicar · 26-Jan-2009, 18:58

0.016 ms demora el mio :P

GNU nano 2.0.7 Fichero: primeTest.java

import java.util.*;
public class primeTest{
public static boolean primes[] = new boolean[20000];
public static void main(String args[]){
Arrays.fill(primes,true);
for(int n = 2;n<=Math.sqrt(primes.length);n++)
if(primes[n])for(int k = n*n;k<primes.length;k+=n)primes[k]=false;
int conta = 1;
for(int n = 3;n<primes.length;n+=2)
if(primes[n])conta++;
System.out.println(conta);
}
}

roguer lo podrias hacer mas rapido, agregale un break cuando le das false al booleano de prime

Monje nunca dijiste nada :P.. todo falso como el de premaraton phone..me quede esperando que calificaras :P

phicar · 28-Jan-2009, 13:42

A pedido de Dragon, Resultados:

roguer
0.612
0.632
0.640
lenguaje:c++
promedio 0.628s

csarlg
0.050
0.040
0.050
lenguaje:c++
promedio 0.046

Mandrake
0.768
0.769
0.770
lenguaje:java
prfomedio 0.769

Radical
0.065
0.072
0.069
lenguaje:c++
promedio 0.068

Phicar
0.316
0.313
0.271
lenguaje:java
promedio 0.300

lo hice con time...les dejo foto...modifique los programas de los que usaron windows un poquito...(basicamente nada) pero para que funcaran toco cambiar un par de lineas que no afectan en nada el algoritmo

*1 no es primo :P
*Zefiro tenia mal el resultado
*Hay ganador java y ganador c++ porque no hay punto de comparacion entre los dos lenguajes en cuanto a velocidad se refiere..memoria contra maquina virtual es como jodido
*Mambru se fue a la guerra, que dolor que dolor que pena

DragoN · 15-Mar-2009, 18:58

GANADORES

Phicar HA GANADO CON JAVA
0.316
0.313
0.271
lenguaje:java
promedio 0.300

csarlg HA GANADO CON C++
0.050
0.040
0.050
lenguaje:c++
promedio 0.046

se les a añadido el premio que en este caso son 10 puntos de reputación, los próximos retos tendrán premios materiales.

jakero · 16-Mar-2009, 18:57

hola q tal, aprovechando este tema me gustaria sabes como se hace el testeo de los codigos, hay programas para hacerlo????

hecky · 16-Mar-2009, 19:08

Como que como se hace el testeo??? lo tienes que compilar

jakero · 17-Mar-2009, 10:11

Si eso creo q ya lo sabia, creo q hice mal la pregunta, yo me referia a como obtienen el tiempo q tarda el programa en hallar los numeros primos... ej
0.050
0.040
0.050

efrajdk · 20-Mar-2009, 17:11

Los números primos desde los tiempos de antigüedad, donde los matemáticos se cuenta que algunos números, son divisibles entre el 1 y los mismos números le consideraron, números primos. En la actualidad los números primos siguen siendo hoy estudiadas, y algunos de los números primos son pueden llenar hojas y hojas, pues constan de millones de dígitos.

En nuestro caso para los programadores, los números primos tiene ciertas aplicaciones, en la criptografía, tales es el uso en la llave RSA, que maneja números primos grandes. Muchos de estos números tienen mas 500 dígitos,.la verificación de números primos son computacionalmente no son posibles pues pueden tardar varios años, por los tanto se inventaron distintos métodos algortimicos de tal modo que no sea engorroso, si no la comprobación de los números primos sea rápida y no lleva mucho tiempo, entre ellos esta el método de Pollard, métodos numéricos la mas usada es el método probabilística, que tiene un algoritmo muy interesante que es específicamente para números que tengan mayor a 100 dígitos. Java en su librería contiene este algoritmo, específicamente esta en la librería esta en BigInteger donde, el método es EsPrimo(BigInteger a) que devuelve mediante el método probabilística en forma true o false.
Los numeros primos fueron atacados desde distintas ópticas de las matemáticas, como analizadores de la algoritmia, también de la teoría de números, para verificar un número primo, pues un numero primo que tiene cerca a 500 digitos y o mas pueden tardar varios años en verificarse.

Uno de los métodos que se usan nórmalmente es dividir sucesivamente el numero que se quiere verificar sucesivamente desde 1 hasta el numero verificar: consideremos x el numero a verificar, entonces en nuestro programa seria:
Sum=0
for(I=1; i<=x;i++)
{if(x%I==0)
sum++;
}
if(sum>=3)
print(no primo)

else
print(primo)

este seria un algoritmo que verifica el numero si es primo o no, pero es muy engorroso y tardad varios segundos, otra idea seria, dividir el numero x/2 de tal modo el algoritmo quedaría:

sum=0
for(I=1; i<=x/2;i++)
{if(x%I==0)
sum++;
}
if(sum>=3)
print(no primo)

else
print(primo)

de manera que este algoritmo mejora por lo menos algunos segundos, pero no es la buena opcion, otra forma de plantearnos y por lo menos la mas efectiva es de la siguiente forma, sabemos que un numero x su raiz es raíz(x): veamos algunos análisis:;
49 su raiz entera es 7
5 su raiz entera es 2
81 su raiz entera es 9
en cada uno de los anteriores ejemplos la raiz va reduciendo de una forma radical las operaciones de comparación que se puede realizar
, esto se puede generalizar de la siguiente forma en un algoritmo:

sum=0
for(I=1; i<=raiz(x);i++)
{if(x%I==0)
sum++;
}
if(sum>=3)
print(no primo)

else
print(primo)

que reduce radicalmente los números de comparaciones, ahora les presento mi algoritmo, que si tiene buenos resultados, por los menos, en el concurso de programación de la ACM donde participe, pero si éxitos algunos, el algoritmo es una modificación a la anterior, pero viene comparando de dos formas, uno va en sentido de avance y el otro en sentido de retroceso, veamos el algoritmo.
sum==0
Inf=1;
sup=raiz(x)

while(sum==0 && inf<=sup+1)
{if(x%Inf==0||x%sup==0)
sw=1;
else
inf++;
sup--;
}
if(sum==1)
print(no primo)

else
print(primo)

entonces nuestro programa seria de la siguuientes forma, con los analisis anteriores y aplicando lla verifiacion del algoritmo de
verificacion de numeros primos, seria de la siguiente forma:
en este algoritmo
cont=1; //inicializamos el contador de numeros primos, pues contamos el dos como primo, y el uno no es considerado primo.
for(i=3; i<=200000;i=i+2)//pues se considera que los multiplos de dos no son primos, entonces solo verificamos 3,5,7,9,11,
{if(veriprimo(i)) //verifica primo si es verdadero el cont aumenta en caso contrario no //ase nada
cont++;
}
print(cont)

aqui el codigo en java

import java.util.*;
import java.math.*;
public class Primo
{
boolean veriprimo (int x)
{
boolean sw = true;
int inf = 2;
int sup = (int) (Math.sqrt (x));
while (sw == true && inf < sup + 1)
{
if (x % inf == 0 || x % sup == 0)
sw = false;
else
{
inf++;
sup--;
}
}
return sw;

}

void calcula ()
{
Date a = new Date ();
int i, s = 1;
for (i = 3 ; i <= 20000 ; i += 2)
{
if (veriprimo (i) == true)
{
s++;
}
}
Date b = new Date ();
System.out.println (b.getTime () - a.getTime ());
System.out.println ("el numero total de primos es " + s);
}

public static void main (String args [])
{
Primo p = new Primo ();
p.calcula ();
}
}

Como escribo por primera vez recibo las criticas y aceptó sugerencias.

efrajdk

Tronador · 31-Mar-2009, 00:39

ya se ha terminado el reto? puedo participar por ejemplo con assembler o python?

si no entonces lo hare solo por diversion xD

Tronador · 05-Apr-2009, 10:43

Código PHP:


			
#include <stdio.h>

#include <stdlib.h>

#include <time.h>

__inline int fsqrt(__int16 numero)

{

   float x = (float)(numero);

   float xhalf = 0.5f * x;

   register int i = *(int*)&x;

   i = 0x5f3759d5 - (i >> 1);

   x = *(float*)&i;

   x = x*(1.5f - xhalf*x*x);

   return (__int8)(1/x);



}

__inline int esprimo(__int16 numero)

{

    register __int8 resultado;

    register __int8 raiz = fsqrt(numero);



    __asm

    {

        mov ax, numero

        mov bl, 2

        mov cx, ax

        mov dl, raiz

        cmp ax, 1

        je noprimo

        cmp ax, 2

        je primo

        div bl

        cmp ah, 0

        je noprimo

        mov bl, 3

        mov ax, cx



    ciclo:

        div bl

        cmp ah, 0

        je noprimo

        add bl, 2

        mov ax, cx

        cmp bl, dl

        jb ciclo

        jmp primo



    primo:

        mov resultado, 1

        jmp fin



    noprimo:

        mov resultado, 0



    fin:



    }



    return resultado;

}

int main(){



    register __int16 numero = 1;

    register __int16 cont = 0;

    clock_t t_ini, t_fin;

    double diff;



    t_ini = clock();

    while(numero < 500)

    {

        if(esprimo(numero) == 1)

        {

            cont++;

        }

        if(numero > 2) numero+=2;

        else numero++;

        

    }

    printf("Hay %d primos entre 1 y 500\n",cont);

    t_fin = clock();

    diff = (double)(t_fin - t_ini);

    printf("%.16g ciclo(s) de reloj\n", diff);





    system("pause");

    return 0;



}

Me gustaria saber si valió la pena y si es mas rapido o solo fue perder tiempo en assembler xD

Lo compile con Visual C++ 2005, y me da 0.001 en mi maquina PERO solo calcula la cantidad de primos entre 1 y 500 (es assembler de 16bits, el maximo numero que se almacena en un registro de 8bits es 511)

Modifique el de cesrlg para que haga lo mismo que el mio (del 1 al 500 y que muestre solo cantidad), asi quedo:

Código PHP:


			
#include <iostream>

#include <cstdlib>

#include <ctime>

using namespace std;





struct nodo{

   unsigned long int val;

   nodo *sgte;

};

int cont = 1;

void calcular_primos(nodo *Raiz, nodo **Final, unsigned long int val);



void main(){

  unsigned long int val = 2;

  nodo *Lista, *Final;

  clock_t t_ini, t_fin;

  double diff;



  Lista = new nodo;

  Lista->val = val;

  Lista->sgte = NULL;

  Final = Lista;



  t_ini = clock();

  while( 1 ){

       calcular_primos(Lista, &Final, ++val);

       if(val == 500){break;} //* Numero limite 100*//

  }

  cout<<"Hay "<<cont<<" numeros primos entre 1 y 500\n";

  t_fin = clock();

  diff = (double)(t_fin - t_ini);

  printf("%.16g ciclos de reloj\n", diff);

  system("pause>nul");

}



void calcular_primos(nodo *Raiz, nodo **Final, unsigned long int val){



  bool es_primo = true;

  nodo *p = Raiz;



  while(p != NULL){

    if(val%(p->val) == 0){

            es_primo = false;

            break;

    }

    if((p->sgte) != NULL){

          if(((p->sgte)->val)*((p->sgte)->val) > val){

                     break;

          }

    }

    p = p->sgte;

  }



  if(es_primo){

         (*Final)->sgte = new nodo;

         ((*Final)->sgte)->val = val;

         ((*Final)->sgte)->sgte = NULL;

         *Final = (*Final)->sgte;



         cont++;

  }



}

cesrlg: 6 ciclos de reloj minimo, 11 ciclos de reloj maximo
mio: 0 ciclos de reloj minimo, 1 ciclo de reloj maximo.