Liczby pierwsze

Question

Próbuję rozwiązać zadanie ze Spoja dotyczące liczb pierwszych. Zarówno kompilator jak i serwis Ideone kompilują poprawnie, a Spoj wyrzuca błąd. Oto mój kod: 

#include <iostream>
#include <math.h>

using namespace std;

int main()
{
    int liczbaTestow, liczba_Dzielnikow, liczby, x;

    cin>>liczbaTestow;

    for(int i = 1; i<=liczbaTestow; i++)
    {
        cin>>liczby;
        x = liczby / sqrt(liczby);

        if(liczby>=2 && liczby % x !=0)
        cout<< "TAK"<<endl;
        else
        cout<< "NIE"<<endl;

    }

    return 0;
}

 

Comments

Jaki błąd?

---

Spoj pokazuje błędna odpowiedź. To wszystko

---

Ah :)

No to udana kompilacja oznacza tylko że program w ogóle ma sens i da się go uruchomić, nie oznacza że sama logika programu ma sens ;)

A jaka jest treść zadania?

---

Sprawdź, które spośród danych liczb są liczbami pierwszymi

Input

n - liczba testów n<100000, w kolejnych liniach n liczb z przedziału [1..10000]

Output

Dla każdej liczby słowo TAK, jeśli liczba ta jest pierwsza, słowo: NIE, w przeciwnym wypadku.

---

No to... powiem tylko, że ten kod nie sprawdza czy liczba jest pierwsza. Polecam po prostu jeszcze trochę poczytać o liczbach pierwszych i ich sprawdzaniu ;)

Answer 1

Kod nie sprawdza czy liczba jest liczbą pierwszą. Polecam przyjrzeć się temu kodowi:

#include<iostream>
#include<cstdlib>
using namespace std;

bool czy_pierwsza(int n)
{
	if(n<2)
		return false; //gdy liczba jest mniejsza niż 2 to nie jest pierwszą
		
	for(int i=2;i*i<=n;i++)
		if(n%i==0)
			return false; //gdy znajdziemy dzielnik, to dana liczba nie jest pierwsza
	return true;
}

int main()
{
	int n;
	
	cout<<"Podaj liczbę: ";
	cin>>n;
	
	if(czy_pierwsza(n)) //lub czy_pierwsza(n)==1
		cout<<"Liczba "<<n<<" jest pierwsza"<<endl;
	else
		cout<<"Liczba "<<n<<" nie jest pierwsza"<<endl;
	
	system("pause");
	return 0;
}

 

Comments

Jeśli liczba nie jest liczbą pierwszą, to jej dzielniki zawsze są wszystkie liczbami pierwszymi bo inaczej dzielniki można przedstawić w postaci iloczynu liczb pierwszych. Sprawdzanie wszystkich dzielników nie ma sensu bo potrwa sto razy dłużej. Matematyka naprawdę przydaje się w szkole.

---

Czytanie ze zrozumieniem także się przydaje w szkole, "Tą drugą opcje można rozwiązać na kilka sposobów, od dzielenia aż po wektory lub nawet rozkłady liczb."

W sumie logicznie każda liczba która nie jest liczbą pierwszą jest liczbą pierwszą, ponieważ przed końcem rozkładu tej liczby zawsze znajduje się liczba pierwsza, czyli przed uzyskaniem jedynki.

---

każda liczba która nie jest liczbą pierwszą jest liczbą pierwszą,

 

Ty się dobrze czujesz?

---

(Logicznie), chyba napisałem paratekstowo? Liczba 21 nie jest liczbą pierwszą, po rozkładzie otrzymujemy: 21 | 3 7 | 7 1 | 0 czyli jak pisałem, przed końcem rozkładu mamy liczbę pierwszą, czyli 7 jest liczbą pierwszą i nawet nie musimy tego sprawdzać.

---

Strona mi rozjechała rozkład :), powinno być:

1. 21 = 3 (początek)
2. 7 = 7 (liczba pierwsza)
3. 1 = 0 (koniec)