liczby pierwsze

Question

Witam 

Chciałem napisać program który wyświetli mi wszystkie liczby pierwsze z zakresu 2...N.Napisałem program który sprawdza czy liczba jest pierwsza i nie wiem co dalej , męczę się z tym zadaniem już dłuży czas i niewiem co robie źle.Czy może ktoś mi pomóc?

pozdrawiam

#include <stdio.h>
#include <stdlib.h>
int main(void)
{
     int p, i;

     printf("Podaj liczbe: ");

     scanf("%d", &p);

     for(i = 2; i < p; i++)

     {

          if(p % i == 0)

          {

               printf("%d  nie jest liczba pierwsza.\n", p);

               system("PAUSE");

               return (1);

          }
          else
          {
                printf("%d jest liczba pierwsza.\n", p);

          }

     }

     return (0);
}

 

Answer 1

Powinieneś mieć dwie pętle, jedną sprawdzającą konkretną liczbę i oraz drugą, wewnętrzną, która będzie służyła do sprawdzania wszystkich dzielników rozpatrywanej liczby i. Zauważ, że jest to podejście naiwne i dla dużych N będzie mało efektywne. Zobacz sito Eratostenesa.

Answer 2

Czy liczba jest pierwsza możesz stwierdzić dopiero po sprawdzeniu wszystkich dzielników, a nie od razu kiedy if się nie spełni. To co masz w else powinno stać za pętlą ;)

Answer 3

- weź wszystko pomiędzy linijką 10 i 33 w pętlę for dającą liczby od 2 do N i sprawdzaj każdą z nich swoim działającym programem,

- po co tam jest to return(1) ???

- sprawdzając podzielniki liczby wystarczy sprawdzić czy dzieli się przez 2, jeżeli nie to odpada co druga liczba do sprawdzenia, poza tym wystarczy sprawdzić podzielność przez liczby z przedziału <2,sqrt(p)> bo jak tam nie będzie dzielników to w przedziale (sqrt(p),p) też ich nie będzie, te dwa zabiegi mocno przyspieszą program bo ilość sprawdzanych liczb spadnie drastycznie,

- pobaw się sitem erastostenesa, ono jest właśnie stworzone do takiego zadania i chyba najszybsze z możliwych opcji,