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

(Trochę niefajnie, że dajesz tak odpowiedź na tacy :/ )

---

Dzięki bardzo. Mam pytanie, dlaczego używamy zmiennej bool?

---

Boolean tylko pokazuje czy liczba pierwsza jest liczbą pierwszą (wtedy boolean jest ustawiony na 1), lub nie jest liczbą pierwszą, czyli (0)

---

Lepiej spojrzeć na gotowy kod, zapamiętać i skumać jak działa niż główkować kilka godzin.

---

Ja bym to trochę poprawił bo skoro mamy sprawdzić dużo liczb to dużo szybciej jest zrobić tak, żeby zrobić tablicę liczb pierwszych do wartości pierwiastek ze stu tysięcy. Można to zrobić sitem Atkina potem przepisać otrzymane liczby pierwsze do tablicy w której są tylko one, i próbować dzielić sprawdzane liczby przez kolejne liczby pierwsze, bo tylko takie dzielniki mają sens.

---

To wtedy nie jest test pierwszości, prawdziwy test pierwszości sprawdza czy liczba jest:

• większa od 1
• która ma dwa dzielniki naturalne, siebie i jedynkę. 

Tą drugą opcje można rozwiązać na kilka sposobów, od dzielenia aż po wektory lub nawet rozkłady liczb.

---

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)