Sprawdzanie czy liczba jest liczbą pierwszą

0

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?

3

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...

3

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

  1. Dla każdej liczby i z przedziału [2; n]
    1. Dla każdej liczby j z przedziału [2; i]
    2. Jeśli j \mid i to przerwij wykonywanie pętli 1.1
    3. Jeśli j \not\mid i 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 \sqrt{n}
  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.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0