Numeros primos

mal4c · 15-Aug-2008, 23:31

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

;D un buen reto escrito por el dragonauta Ric_Monje, gracias por el.

Bueno señores, veo que aki la gente se limita a a pstear vinculos de paginas, y muy pocos a redactar articulos o mini tutoriales, pero en este moento vengo es a proponerles una pequeño concurso, la idea es qu dirante los proximos dias, todo el que desee participar postee un metodo encargado de hallar los numeros primos del 1 al 20.000, el concurso lo gana el que lo haga en el algritmo que lo haga en el menor tiempo posible..que les parece...animence, por lo menos nos entretenemos un rato Tongue

Con esto nos enseñamos no solo a desarrollar x cosa, sino a hacerla lo más eficiente posible. Las aplicaciones concursantes serán compiladas y ejecutadas en la misma pc, para que no haya problema.. échenle lógica pues, quiero ver a varios de aqui inscritos, he visto que varios juegan con java. Lo mejor seria ver al menos 5 propuestas.

pd. esto también es oportunidad para los que quieran iniciarse en java puesto que es sencillo este desafío por parte del lenguaje..

Cita:

Código:
public class Primo{
public void numeros(){
for(int i=0; i<=20000;i++)primos(i);
}
public void primos(int n){
..............
...........
......... //Al final pondre el mio :P
.......
....
..
public static void main(String args[]) {
Primo p = new Primo();
long inicial=System.nanoTime(); //Usare el metodo nanoTime() para medir el tiempo.
p.numeros();
System.out.println((System.nanoTime()-inicial)*0.000000001);
}
}

dragonuta que lo acepta ratahack, ;D ;D

Cita:

Mi idea es crear un contador del 1 al 20.000 que se guarde en la variable “x”
Luego esa variable “x” se pasara a dividir entre los principales números primos Ej.: 2, 3, 5, 7, 11, 13, 17,19 luego si el resto de la división es = a 0 pasara a contarse. ya que cada numero mencionado tendrá una variable especifica. Esto con la finalidad de que si un número dividido entre los ya mencionados nunca su resto es 0 es porque, lo más probable, sea un número primo.

Pero como hacemos para contar los primos?

Si el tope que es 20000 le restamos todas las cantidades de números acumulados cuyo resto dio 0 para ver cual es la diferencia. Y esa diferencia son todos esos números primos. Aquí puse pongo un ejemplo programado con visual Basic:

Private Sub Command1_Click()

For x = 1 To 20000

If x Mod 2 = 0 Then
i = i + 1
ElseIf x Mod 3 = 0 Then
o = o + 1
ElseIf x Mod 5 = 0 Then
p = p + 1
ElseIf x Mod 7 = 0 Then
k = k + 1
ElseIf x Mod 11 = 0 Then
q = q + 1
ElseIf x Mod 13 = 0 Then
r = r + 1
ElseIf x Mod 17 = 0 Then
z = z + 1
ElseIf x Mod 19 = 0 Then
b = b + 1
End If

Next

alex = 20000 - (o + i + p + k + q + r + z + b) + 8

Text1.Text = alex

End Sub

Esto dará la respuesta en cuadro de texto llamado Text1.
Discúlpenme si esta mal redactado y acepto todas las sugerencias posible ya que me estoy iniciando en el mundo de la programación.

Aduxer no se quedo atras bien por el :

;D

su aporte fue:

Bueno Amigos aquiles dejo el codigo escrito en c para hallar los numeros primos!!
en determinado dominio!

Cita:

#include <stdio.h>
#include <conio.h>

void primos (int n1)
{
int aux,i,j;
for (i=1;i<=n1;i++)
{
/* Estudiamos si el numero 'i' es primo o no. Para ello contabilizamos sus divisores.*/

aux=0;
for (j=1;j<=i;j++)
{
if (i%j==0)
aux++;
}
/* Todo numero es divisible entre 1 y entre si mismo; por tanto, si el numero total de divisores
Es igual a 2, el numero es primo. */
if (aux==2)
printf("%d\n",i);
}
}

int main()
{
int n1;

do
{

printf("Introduce un numero mayor que cero: ");
scanf("%d",&n1);
}while(n1<1);
printf("Los numeros primos entre 1 y %d son:\n",n1);
primos(n1);

getch();
return 0;
}

y Yshua, por que las pequeñas ideas tambien son grandes soluciones, su aporte:

acabo de ver este post. tengo una pequeña idea. la voy a probar y la posteo, mientras se me ocurre algo mejor.

EDITADO

OK.
ya implementé mi idea.

Cita:

Código: (java)
public static boolean primo(int x){
if(x==1)return false;
if(x==2)return true;
if(x%2==0)return false;
else{
for(int i=3;i<x;i+=2){
if(x%i==0)return false;
}
}
return true;
}

el metodo retorna true si x es primo así que el main cambiaria por este
Código: (java)
public static void main(String[] args) {
for(int i=0;i<20000;i++)
if(primo(i))System.out.println(i+" ");

}

Tengo otra idea, no se si mas rápida o lenta. pero ahora la pongo también

ExtreamShocker · 18-Aug-2008, 15:02

Escrito por Mandrake originalmente ahora llamado en los bajos mundos como ExtreamShocker

Bueno ya termine mi codiguin¡¡¡¡ , a ver que tal les va con esto 8)

Código:

Código:

public class Primo {
      public static void main(String[] args) {
          int j=2;
          boolean p=true;
          System.out.print("1\n2\n3\n");
          long inicial=System.nanoTime();
          for(int i=5;i<20000;i+=2)
          {    
              for(int k=2;k<=j;k++)
              {
                  if(i%k==0)
                  {    
                      p=false;                      
                      break;
                  }                  
              }
              j++;
              if(p)
                  System.out.println(i);
                p=true;
          }
        System.out.println((System.nanoTime()-inicial)*0.000000001);
    }
}

Solo como sugerencia para calcular el tiempo, para ver cual es mas rapido, se podria tomar 10 tiempos de cada codigo y elegir el mas bajo de las 10 mediciones, asi para cada codigo, ya que al estar ejecutando varias veces el codigo me di cuenta que el tiempo en que tardaba en ejecutarse variaba.

P.D.:El codigo que mide el tiempo fue utilizado del ejemplo que dieron como referencia

DragoN · 18-Aug-2008, 15:47

de momento hay 3 códigos para competir entre si, esperemos unos cuantos mas para realizar las primeras pruebas, luego se les da los resultados de sus códigos y un tiempo para mejorarlo si desean, después se realiza la prueba final y se anuncia el ganador.

Dodisk2 · 17-Sep-2008, 00:14

que paso con los otros programadores antes de lo sucedido en el foro habian mas de los que hay ahora

zefiro · 22-Sep-2008, 01:03

jaja, que entrete

, primero que todo hola, y segundo no soy programador pero quise aportar, la verdad me he entretenido bastante con esto de los "retos"

, primero el codigo

Código:

#include <stdio.h>

main ()
{

int n,i,cont=0;
float div3,div5,div7,div9;
for (n=0;n<10000;n++)
{
    i=2*n+1;
    div3=i%3;
    div5=i%5;
    div7=i%7;
    div9=i%9;
    if( (div3!=0) && (div5!=0) && (div7!=0) && (div9!=0))
    {
        cont++;
    }
}
printf("N° total de Primos %d\n",cont);
}

segundo lo que se demoro poco, pero hay que hacer las mediciones en pc del mismo calibre, tengo un amd64 3000+ con 1 gb

Código:

zefiro@slack:~$ nano primos.c 
zefiro@slack:~$ cc primos.c -o primos
zefiro@slack:~$ time ./primos
N° total de Primos ####

real  0m0.002s
user  0m0.003s
sys   0m0.000s
zefiro@slack:~$

ExtreamShocker · 30-Sep-2008, 01:36

zefiro!!!!!

yo lo habia intentado ya asi, pero otro concursante me aclaro que estaba malo ese algoritmo, empieza aceptando numeros primos que no lo son, yo tambien pensaba que si el numero no era divisible entre 3,5,7,9 deberia ser primo, :-[ pero lamentablemente eso no fue asi , como ejemplo mira el numero 121 es un numero que no es divisible entre 3,5,7,9 pero si lo es entre el numero primo 11, ya que 121 mod 11 =0,lo cual tu algoritmo lo reconoce como num primo,pero no lo es!! y si te das cuenta 11 es primo tambien, entonces no solo tenes que ver si es divisible entre 3,5,7,9 , sino que tambien entre los mismos primos!!!!

00000000 · 30-Sep-2008, 22:30

aca esta el mio en c++

Código:

#include <iostream.h>




unsigned long pro(int divisor );
int n;
int i;
 int numero,divisor;
main ()

{
   system("color 0a");
int a,b;  
   cout<<"ingrese un numero"; 
   cin>>numero; 
 
   n = pro(numero);
   
   }
 
unsigned long pro(int divisor )
 
   {
         for (i=numero;i<=20000;i++)
         {
                 for(divisor=2; (divisor*divisor<=i)&&(i%divisor!=0); divisor++)
 {
 }
 if (divisor*divisor>i) 
 {
 cout<<"  "<<i<<endl;

 
 numero = numero +1;
 
 
}
                
                   }

       
system("pause");
 return 0;
         }

anexo un video que hize comparando mi code con el de otro y bueno el mio salio mas rapido

csaralg · 12-Nov-2008, 10:50

Hola, hace algún tiempo hice este algoritmo para calcular los primos y es bastante rápido. Se trata de crear una lista enlazada con los números primos. Inicialmente solo se le agrega el 2 luego dentro de un bucle se llama a una función que trata de añadir los siguientes números (3, 4, 5 ,6...) a la lista pero solo se añaden los primos. La lista también sirve para comprobar que un numero es primo. Esto es si un numero no es múltiplo de ningún elemento de la lista entonces es primo. Para hacerlo mas eficiente se añade otra optimizacion para que no evalue la multiplicidad con todos los elementos de la lista sino solo con aquellos cuyo valor multiplicado por 2 sea menor o igual al numero.

Datos Adicionales:
Lenguaje: C++
SO: Windows
Compilador: Dev-C++ Version 4
Tiempo en resolver el reto: un par de segundos.

Código:

#include <iostream.h>
#include <stdlib.h>


struct nodo{
   unsigned long int val;
   nodo *sgte;
};

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

void main(){
  unsigned long int val = 2;
  nodo *Lista, *Final;

  Lista = new nodo;
  Lista->val = val;
  Lista->sgte = NULL;
  Final = Lista;

  cout<<val<<" ";

  while( 1 ){
       calcular_primos(Lista, &Final, ++val);
       if(val == 20000){break;} //* Numero limite 100*//
  }
  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;

         cout<<val<<endl;
  }

}

//Comentario: Modifique el algoritmo para que sea mas rapido. (¿se vale?)

DragoN · 25-Nov-2008, 11:36

Bueno ya hay varios competidores... ¿les parece si empezamos a testear?

chakuako · 25-Nov-2008, 21:39

Si! Que comienze el testeo!! ;D ... Veremos quien gana :P