Sprawdzanie czy liczba jest liczbą pierwszą

Witam!
Chcę napisać program, który wypisuje z danego przedziału liczby pierwsze.
Napisałem tyle:

 #include <stdio.h>
#include <stdlib.h>

int main()
{
    
    int x,n,i,j;
    
    scanf("%d", &n);
    
    for(i=2; i<=n; i++)
    {
        
        for(j=2; j<i; j++)
        {
            
            if (i%j==0)
            {
                break;
                
            }
            else
            {
                
                
                printf("%dn", i);
                break;
            }
        }
        
        
    }
    
    
    return 0;
}

Do pewnego momentu działa dobrze, ale potem wypisuje np. 21 która nie jest liczbą pierwszą. Dlaczego tak się dzieje?

Bo to co napisałes nie ma sensu? Nie będę sie tu nawet rozwodził na tym że szukasz dzielników powyżej pierwiastka z X... Popatrz co robisz -> sprawdzasz czy twoja liczba dzieli sie przez kolejne dzielniki. Jeśli sie dzieli przez i-tą liczbę to kończysz pętlę, a jeśli się nie dzieli to wypisujesz tą liczbę. Tylko że wypisać możesz dopiero jak sprawdzisz WSZYSTKIE dzielniki a nie jeden. Twój program działa źle już dla 9, która nie jest pierwsza...

Prześledźmy co Twój (strasznie nieoptymalny kod) robi:

1. Dla każdej liczby z przedziału
2. Dla każdej liczby z przedziału
3. Jeśli to przerwij wykonywanie pętli 1.1
4. Jeśli to wypisz liczbę na ekran i przerwij wykonywanie pętli 1.1

Widzisz gdzie masz błąd? Nie ważne co zrobisz to zawsze wychodzisz z pętli 1.1, czyli de facto sprawdzasz czy liczba jest nieparzysta i wtedy ją wypisujesz na ekran.

Jednak ten kod jak napisałem na początku jest bardzo nieoptymalny. Najważniejsze rzeczy do zapamiętania:

1. Wszystkie dzielniki liczby, które są istotne w przypadku pierwszości są mniejsze od
2. Szukanie dzielników jest czasochłonne, szukanie w pamięci nie.
3. Istnieją metody wyszukiwania liczb pierwszych w zakresie (hasło: sita). Sito Eratostenesa w twoim przypadku powinno być dostatecznie wydajne.