[C++] Liczby którymi pierwiastkami są liczby pierwsze


(adriano765) #1

Mam problem z programem który znajduje liczby którego pierwiastek kwadratowy jest liczbą pierwszą. Z pośród liczb w pliku program znajduje tylko 169 i wpisałem tam inne liczby spełniające te warunki.

#include 

#include 

#include 

using namespace std;


int main()

{

    int a,b,d2=0,d3=0,d5=0;

    ofstream zapis ("zapis.txt");

   fstream plik ("liczby.txt");


    while (plik >> b)

    {

        a=sqrt(b);

       d2=a%2;

       d3=a%3;

       d5=a%5;

       if (d2==0 || d3==0 || d5==3)

        {

        zapis << b << " ";

        cout << b << "\t";

    	}

	}

plik.close();

zapis.close();

return 0;

}

(Razi) #2
  1. Zapisując wynik z sqrt w int, tracisz ułamek. jeśli jest ułamek - nie ma co mówić o liczbie pierwszej, a taki algorytm może wtedy dać wynik fałszywie pozytywny, np. √10≈3,162, po zrzuceniu do int - 3, a 3 jest liczbą pierwszą.

  2. Zakładasz za liczby pierwsze tylko 2, 3 i 5, nie sprawdzasz podzielności przez 7, 11, 13, 17, 19, 23…

Poza tym, (d2==0 || d3==0 || d5==3) - co to za warunek? Tym szukasz liczby które są podzielne przez 2, 3 lub reszta z dzielenia przez 5 daje 3.


(adriano765) #3

Dzięki za porady a jak próbuję podzielić modulo liczbę rzeczywistą przez całkowitą to wyrzuca błąd że tak nie można.

error: invalid operands of types ‘float’ and ‘int’ to binary ‘operator%’


(Rolek0) #4
#include 

#include 

using namespace std;


int main()

{

	int x;

	while(cin >> x)

	{

		if(x % 2) //tylko liczby nieparzyste, bo większość liczb pierwszych jest nieparzysta a kwadrat liczby nieparzystej też jest nieparzysty

		{

			int r = sqrt(x);

			if(r * r == x) //tylko kwadraty liczb całkowitych, jeśli kwadrat obciętego pierwiastka jest równy danej to dana jest kwadratem liczby całkowitej

			{

				//sprawdzanie pierwszości

				int l = sqrt(r); //nie ma sensu sprawdzać podzielności przez liczby większe od pierwiastka

				if(l * l != r) //drobna optymalizacja

				{

					bool p = true;

					for(int i = 3; i <= l; i += 2) //najprostszy sposób sprawdzania pierwszości

						if(r % i == 0)

						{

							p = false;

							break;

						}

					if(p)

						cout << x << endl;

				}

			}

		}

		else if(x == 4) //wyjątkiem jest 4, która jest kwadratem 2

			cout << x << endl;

	}

	return 0;

}

PS. Liczby , których pierwiastkami są liczby pierwsze. :wink:


(adriano765) #5

tylko mam problem z tym wersem if(a%i==0)

#include 

#include 

#include 

using namespace std;


int main()

{

    float a,b;

    ofstream zapis ("zapis.txt");

   fstream plik ("liczby.txt");


    while (plik >> b)

    {

    bool pierwsza=true;

    a=sqrt(b);

	for(int i=2;i
    {

    if(a%i==0)

    {

    pierwsza=false;

    break;

    }

	else pierwsza=true;


    zapis << b << " ";

    cout << b << "\t";

    }}

plik.close();

zapis.close();

return 0;

}

[/code]

(Razi) #6

Bo teraz a zapiszujesz do floata, a modulo z floata się nie robi. Rolek dał dobry przykład z pominięciem liczb rzeczywistych.