chce napisać program w C który sprawdza czy podana liczba jest liczbą pierwszą czy nie.Napisałem coś takiego lecz wiem że coś tu nie gra.wien że trzeba użyć pętli tylko nie mam wizji jak napisać ten program .
#include <stdio.h>
#include <stdlib.h>
main(){
int liczba1,dzielnik=2,wynik1;
printf("podaj liczbe\n");
scanf("%d",&liczba1);
wynik1=liczba1%dzielnik;
if(wynik==0)
else
printf("liczba nie jest pierwsza\n");
return 0;
}
Żeby sprawdzić czy liczba jest pierwsza napisz pętle, która będzie szła od 0 do liczba/2 2 do sqrt(liczba) i próbuj liczba podzielić przez aktualny indeks w pętli. Jeżeli wynik będzie całkowity, to znaczy że liczba nie jest pierwsza i kończysz pracę programu, wyświetlając wcześniej komunikat.
Podpowiedź korzystaj z typu zmiennej która pozwoli przechowywać liczby wymierne, inaczej w wyniku dzielenia zawsze wyjdzie liczba całkowita.
Żeby sprawdzić czy liczba nie jest całkowita możesz zrobić na kilka sposobów, np. podzielić z resztą przez 1.0 i sprawdzić czy wynik równy 0, albo sprawdzić czy wynik zaokrąglony w dół jest równy wynikowi niezaokrąglonemu itd.
możesz prościej mówić
Zellus napisał(a):
... napisz pętle, która będzie szła od 0 do liczba/2 i próbuj liczba podzielić przez aktualny indeks w pętli ...
Zellus napisał(a):
Żeby sprawdzić czy liczba nie jest całkowita możesz zrobić na kilka sposobów, np. podzielić z resztą przez 1.0 i sprawdzić czy wynik równy 0, albo sprawdzić czy wynik zaokrąglony w dół jest równy wynikowi niezaokrąglonemu itd.
Ogólnie to nie wiem czy chwalić czy ganić za to że odwalasz za kogoś część teoretyczną, ale na pewno nie należy dzielić przez 1.0
Przez 1 zresztą też.
A o reszcie z dzielenia koledzy pamiętają? jak będzie równa 0, to znaczy że podzielna. Swoją drogą można by np sprawdzić podzielność przez 2, i potem iterować w pętli tylko po nieparzystych od 3-jki (jak dzieli się przez parzysty dzielnik to przez 2 też)
Swoją drogą można by np sprawdzić podzielność przez 2, i potem iterować w pętli tylko po nieparzystych od 3-jki (jak dzieli się przez parzysty dzielnik to przez 2 też)
Był taki koleś, Ἐρατοσθένης się nazywał, co już ponad 2000 lat temu wymyślił, które liczby trzeba sprawdzać.
Sito Eratostenesa raczej służy do wyłapywania liczb pierwszych niż do sprawdzania czy dana liczba jest pierwsza. Łatwiej będzie zaimplementować coś takiego:
Skorzystaj z:
jeśli m jest dzielnikiem n, to n % m == 0;
Uświadom sobie, że:
Zakładamy, że liczba 1 jest dzielnikiem każdej liczby, więc wystarczy, że do zadanej liczby znajdziemy chocby jeszcze jeden dzielnik z przedziału <2,n-1> (zakładamy, że "n" dzieli "n", więc nie trzeba szukać w przedziale <2,n>) i wtedy udowodnimy, liczbą pierwszą NIE JEST. Co następuje w przeciwnym wypadku to raczej wiemy.
Zgodzę się że sito to przy dużej ilości liczb do sprawdzenia. Ale do samego n-1 sprawdzać nie trzeba, bo np skoro 15 / 5 daje 3, to automatycznie dzieli się też przez 3 (i daje 5). Zatem starczy sprawdzić do pierwiastka z liczby (jak jest liczbą całkowitą to liczba nie jest pierwsza, bo jest jej dzielnikiem) jak żadna mniejsza liczba nie jest dzielnikiem, to pomiędzy pierwiastkiem a liczbą też żadnego nie znajdziemy. Zatem liczba jest pierwsza, o ile nie ma pierwiastka będącego liczbą całkowitą, ani dzielników między jedynką i pierwiastkiem.
edit: no chyba że mamy do sprawdzenia jakąś dużą liczbę, to wtedy sito do jej pierwiastka i sprawdzany wszystkie pierwsze mniejsze od niego (zakładając że takowy jest ułamkowy).
edit2: znana jest maksymalna liczba do sprawdzenia? może dało by się wstawić do programu gotową tablicę liczb pierwszych, to znacznie przyśpieszyło by sprawdzanie.