[C++] Program sprawdzający czy liczba jest pierwsza-problem

Dla specjalistów Programowanie
#1 
#include

#include

using namespace std;

int x;

int opcja;

bool pierwsza(int xwar)

{


             for(int i=1; i
             {

                     if(x%i==0)

                     {

                               return false;

                               }

                               else

                               {

                                   return true;

                                   }

                               }

                               }

                               int main()

                               {

                                   cout<<"PROGRAM SPRAWDZAJACY CZY LICZBA JEST PIERWSZA"<
                                   cout<<"PODAJ LICZBE"<
                                   cin>>x;

                                   if(pierwsza(x))

                                   {

                                                  cout<<"Liczba jest pierwsza"<
                                                  }

                                                  else

                                                  {

                                                      cout<<"Liczba nie jest pierwsza"<
                                                      }

                                                      cout<<"Czy chcesz sprawdzic jeszcze jedna liczbe? 1.Tak 2.Nie"<
                                                      cin>>opcja;

                                                      switch(opcja)

                                                      {

                                                                   case 1: main();

                                                                   break;

                                                                   case 2: exit(0);

                                                                   break;

                                                                   }

                                                                   getch();

                                                                   }

Program stwierdza, że kazda liczba nie jest pierwsza. Nie wiem czemu, bo przeciez podczas każdego wykonania for sprawdza, czy reszta dzielenie to 0… Może i ustawic na 2, i dac jakis break, ale nic mi to nie pomogło. Wskażcie błąd.

#2

Ułóż ten kod bo nie da się tego czytać :frowning:

Może coś poknociłeś z klamrami, najpierw ułóż

edit: Ułożyłem ci kod i znalazłem ciekawą rzecz:

for(int i=1; i

{

if(x%i==0)

W tych liniach powinieneś użyc xwar skoro taka zmienna zadeklarowales sobie

Swoja droga, takie zagranie nie ma sensu ponieważ starczy że liczba dzieli się przez 1 (wszystkie sie dziela…) to wyjdzie return true i kazda będzie pierwsza.

Lepszym sposobem było by zrobic zmienna np int temp; i jeśli licba jest podzielna przez i dodac do niej jeden (np temp++). Pod koniec funkcji sprawdzic, jesli temp == 0 to true, jesli jednak nie to false. No i lepiej zaczynac pętle od 2 a nie od 1.

Cały kod ułożony z wprowadzona poprawka (bez nowego algorytmu, nic sie nie nauczysz gdy ktos ci go napisze):

#include

#include

using namespace std;

int x;

int opcja;

bool pierwsza(int xwar)

{

	for(int i=1; i
	{

		if(xwar%i==0)

		{

			return false;

		}

		else

		{

			return true;

		}

	}

}

int main()

{

	cout<<"PROGRAM SPRAWDZAJACY CZY LICZBA JEST PIERWSZA"<
	cout<<"PODAJ LICZBE"<
	cin>>x;

	if(pierwsza(x))

	{

		cout<<"Liczba jest pierwsza"<
	}

	else

	{

		cout<<"Liczba nie jest pierwsza"<
	}

	cout<<"Czy chcesz sprawdzic jeszcze jedna liczbe? 1.Tak 2.Nie"<
	cin>>opcja;

	switch(opcja)

	{

		case 1: main();

			break;

		case 2: exit(0);

			break;

	}

	getch();

}
#3

poprawiona funkcja sprawdzająca, zaczynamy od 2 bo inaczej żadna nie będzie pierwsza, zwracanie prawdy wyrzucone za pętlę, dodatkowo sprawdzanie czy x nie jest 0 lub 1 (oczywiście nie są pierwsze):

bool pierwsza() //bo po co ten xwar skoro nawet go nie używasz

{

    if (x==1 or x==0)

    {

        return false;

    }

    for(int i=2; i
    {

        if(x%i==0)

        {

            return false;

        }

    }

    return true;

}

i oczywiście na dole

if(pierwsza()) //bez x

bo wywali too many arguments.

@down

sorry, nie zauważyłem Twojego posta, w każdym razie jak będzie chciał to przeczyta parę razy i się nauczy, a jak będzie sam kombinował 5 lat i nic nie wymyśli to się jeszcze może zniechęcić :slight_smile:

#4

A mówiłem, że nic się nie nauczy jeśli ktoś mu pod nos podsunie gotowca.

#5

I tak przy tym programie jest jeszcze sporo roboty :slight_smile:

@szalus94

Ten program trzeba napisać tak, żeby radził sobie z dowolnie dużymi liczbami (liczby muszą być przechowywane jako ciągi znaków). Poza tym można rozejrzeć się za gotowymi algorytmami wyszukiwania liczb pierwszych, bo ten użyty jest niewydajny (choć rozumiem, że to na razie testowy program). Przykładowo sprawdzamy liczbę 13. Wiemy, że nie jest podzielna przez 2 i 3, nie ma więc przykładowo sensu sprawdzać, czy jest podzielna przez 6.

Jakbym sobie pisał ten program, nie zwracając uwagi na istniejące gotowe algorytmy, to robiłbym tak, że najpierw sprawdzam, czy liczba jest podzielna przez 2 (wtedy, gdy ostatnia cyfra tej liczby to 0,2,4,6 lub 8 ), 3 (liczba jest podzielna przez 3 jeśli suma jej cyfr jest podzielna przez 3) oraz 5 (ostatnia cyfra to 0 lub 5), a następnie sprawdzałbym sobie resztę z dzielenia przez wykryte uprzednio liczby pierwsze, czyli dla przykładu przyjmijmy, że sprawdzana jest liczba 13. Sprawdziłem już, czy jest podzielna przez 2,3 oraz 5, i nie jest. Teraz sprawdzam, czy jest podzielna przez 7 oraz 11 i nie jest, a więc 13 to jest liczba pierwsza. (Jakbyś ktoś zauważył tutaj błąd w algorytmie to niech napisze)

EDIT:

Eh nie do końca zrozumiałem problem. Nie wiem skąd mi się wzięło, że chcesz wyszukiwać liczby pierwsze. Mój błąd … No ale skoro już o tym pisałem to w tym algorytmie, który sobie wymyśliłem powyżej należałoby na pewno przynajmniej jedną rzecz zmienić. Nie trzeba sprawdzać, czy dana liczba jest podzielna przez uprzednio znalezione liczby pierwsze. Wystarczy utworzyć sobie jakiś słownik przechowujący wartości będące kwadratem poszczególnych liczb pierwszych.

Czyli w przypadku np. liczby 13 najpierw należy sprawdzić, czy znajduje się ona w tym słowniku. Nie ma jej (bo kwadrat żadnej wcześniej znalezionej liczby pierwszej nie jest równy 13), więc sprawdzamy, czy jest podzielna przez 2,3 oraz 5. Nie jest, więc jest liczbą pierwszą i tym samym do słownika należy dodać wartość 169. W przypadku np. liczby 49 sprawdzamy, że jest ona w słowniku, a więc nie jest liczbą pierwszą. Po tym sprawdzeniu liczbę tę można usunąć ze słownika. Zawsze mniej danych w pamięci.

#6

Przykładowy kod (z biblioteki GMP)

int is_prime(unsigned long int n)

{

	unsigned long int q, r, d;


	if(n < 3 || (n & 1) == 0)

		return n == 2;


	for(d = 3, r = 1; r != 0; d += 2)

	{

		q = n / d;

		r = n - q * d;

		if (q < d)

			return 1;

	}

	return 0;

}

Żeby się nie powtarzać, odsyłam tutaj: http://sawyer.jogger.pl/2010/02/10/naiw … erwszosci/

#7

A po co sprawdzać podzielność przez 5, 7 czy 11, skoro to liczby większe niż pierwiastek kwadratowy z 13? :slight_smile:

Nie bardzo rozumiem do czego miałby służyć słownik znanych już liczb pierwszych?

IMHO, liczby <= 3 trzeba sprawdzić na sztywno, liczby podzielne przez 2 i 3 wykluczyć na dzień dobry, a resztę testować w pętli od 5 do pierwiastka z badanej liczby iterując co 6, badając podzielność przez iterator oraz iterator + 2.