Zadanie programowanie c++ liczby pierwsze

Question

Treść zadania: Napisz program, za pomocą którego otrzymasz tylko te liczby z pliku liczby.txt, które są kwadratami liczb pierwszych.

Nie potrafię znaleźć błędu przez który wynik jest totalnie nieprawidłowy.

#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

bool czy_pierwsza(int liczba)
{
	if(liczba<2)
	return false;
	
	for(int i=2;i<sqrt(liczba);i++)
	{
		if(liczba%i==0)
		return false;
	}	
	return true; 
}


int main(int argc, char** argv) {
	
	ifstream infile("liczby.txt");
	int liczba;
	int liczba2;
	for(int i=0;i<500;i++)
	{
		infile >> liczba;
		liczba2=sqrt(liczba);
		
		if(czy_pierwsza(liczba2))
		{
			cout<<liczba<<endl;
		}		
	}
	
	
	return 0;
}

 

Comments

Czemu limitem w zakresie fora jest pierwiastek z liczby wejściowej? Liczba pierwsza to taka, która dzieli się wyłącznie przez 1 i samą siebie.

---

ponieważ pierwiastek z tej liczby to ostatnia liczba, która może być dzielnikiem liczby.

Patrzyłem to z algorytmem na liczby pierwsze nie ma problemu tylko gdzies dalej.

---

Zobacz co zwróci czy_pierwsza(25)

---

Pomysł z pierwiastkiem jest ok, ale pierwiastek też może być podzielnikiem, czyli nierówność powinna być nieostra.

Mam wątpliwości co do tego dalszego pierwiastkowania - sprawdzenia czy pierwiastek z liczby jest liczbą pierwszą. Pamiętaj, że używasz liczb całkowitych, a pierwiastek z liczby całkowitej zwykle nie jest całkowity. Masz tam przybliżenie.

Answer 1

Tak jak powyżej, nierównośc w funkcji sprawdzającej pierwszość musi być nieostra; a drugi bug jest w main: musisz sprawdzić czy liczba jest perfect square.

#include <iostream>
#include <fstream>
#include <cmath>


using namespace std;


bool czy_pierwsza(int liczba)
{
    if(liczba<2)
        return false;
     
    for(int i = 2;i <= sqrt(liczba);i++)
    {
        if(liczba % i == 0)
        return false;
    }   
    return true; 
}
 
 
int main(int argc, char** argv) {
     
    ifstream infile("liczby.txt");
    int liczba;
    for(int i = 0 ;i < 500;i++)
    {
        infile >> liczba;
        if (ceil((double)sqrt(liczba)) == floor((double)sqrt(liczba)))
        {
            if(czy_pierwsza(ceil((double)sqrt(liczba))))
            {
                cout<<liczba<<endl;
            }       
        }
    }
    return 0;
}

https://www.geeksforgeeks.org/check-if-given-number-is-perfect-square-in-cpp/

https://en.wikipedia.org/wiki/Square_number