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

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

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.

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.

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;
}