Foro de elhacker.net

Buenas, estoy intentando hacer un programa que halle los numeros primos entre 0 y n, ya se que ha salido mas de una vez en el foro y que habrá mucha información por ahí sobre este problema. Ya he estado leyendo algunos posts anteriores y basandome en ellos hice esto, que es la parte prinicpal del programa, el resto da igual ahora mismo:

for(j= 3; j <= num; j += 2){
        for(i = 3; i <= j; i++){
            if((j%1) == 0 && (j%j) == 0 && (j%i) == 0)
            printf("\n%d\t", j);
        }
    }

En este codigo, con el 15 por ejemplo, se realiza la comprobacion 13 veces (desde 3 a 15, ambos inclusive), 3 de ellas son verdaderas (i=3; i=5; i=15) y el resto son falsas. Digo esto porque con esta comprobacion el 15 sale 3 veces, y que tampoco me valdria poner:

 if((j%1) == 0 && (j%j) == 0 && (j%i) != 0)

Porque saldría el resto de las veces, es decir, 10.

También probé a poner:

if((j%1) == 0 && (j%j) == 0)

El problema es que esta condicion la cumplen todos los numeros, no solo los primos, lo que pasa es que lo que caracteriza a los numeros primos es que solo cumplen esas dos condiciones, lo que quiero decir es que no logro aislar los numeros que solo cumplan esas dos condiciones, que son los que yo busco.

Un saudo

if((j%1) == 0 && (j%j) == 0)

Esta condición es absurda. Cualquier número mayor que 0 cumple que es divisible entre 1 y entre si mismo.

Ya, pero en el momento en el que la puse no me di cuenta  :xD

Aunque en verdad, esa condición debe de ser la única que cumplan los números primos y es lo que no se hacer, como aislar los numeros que solo cumplen esa condicion y ninguna mas.

Un saludo.

Solo tienes que utilizar un bucle que se repita mientras el residuo de la división "N / contador" sea diferente de cero con el contador iniciando con el valor dos y terminando de forma natural con el valor N si el numero es primo (si tiene un valor menor significa que no lo es).

Un ejemplo:

int i;
int j;
 
for (i = 2; i < 100; i++){
   for (j = 2; i % j != 0; j++)
      ;
 
   if (j == i)
      printf("%d\n", j);
}

Esa es la forma mas fácil pero menos eficiente, ejemplos sobre como reducir el numero iteraciones los puedes consultar mediante el motor de búsqueda de los foros.

Un saludo

Pueder reducir a la mitad, poniendo for (j = 2; i % j != 0 && j<i/2; j++) por ejemplo. O j<=sqrt(i)

También puedes ir almacenando un vector de números primos, y luego sería comprobar si es divisible entre esos números.

Pero para números pequeños, la solución que puso rir3760 sobra.

recomiendo

for(actual  =3; actual <= maximo; actual = actual + 2){
   for(comprobador=3; comprobador <=(int) raiz(actual);comprobador = comprobador +2){
    
//codigo

}}
eso debería darte una eficiencia bastante alta (sorry por no usar geshi, estoy en el cel y es complicado)

solo pasa por impares y la verificacion solo por impares y solo hasta la raiz del número

Has puesto el dedo en la llaga: si es primo los divisores, sin contar el 1 y al propio número son cero, si no no es primo.

Como ves todo se reduce a ver si tiene algún divisor, cosa que previamente no sabes y habrá que ir comprobando para cada número.

Te paso un código comentado con esa idea.

 Ya lo de ir de dos en dos recorriendo sólo los impares o llegar tan sólo hasta sqrt(i) o mejor, porque no usamos la librería math para sqrt, hasta j*j<=i, son detalles de mejorar la eficiencia pero creo que no era esa la cuestión.

#include <stdio.h>
 
int main(){
  int i,j,num=15,aux=0;
  printf("2  ");/** supuesto num>1 **/
  for (i=3; i<=num;i+=2) {
    aux=0;
    for (j=3;j*j<=i;j+=2){
 /** Aqui si tiene un divisor no es primo y pongo aux a 1
 para saberlo y rompo el bucle ya que no tiene mayor importancia
 que tenga mas divisores **/
      if (i%j==0){
        aux=1;
        break;
      }
    }
/** Aqui si aux=0 es que no tiene divisores y por tanto es primo **/
    if (aux==0)
      printf ("%d  ",i);
  }
  return 0;
}