438 - Liczby pierwsze: gdzie jest błąd?

Question

Witam, zacząłem rozwiązywać problem 438-Liczby pierwsze na SPOJ'u. Sprawdzałem mój kod na wiele sposobów i na każdy działa, lecz maszyna na stronie ciągle wywala mi komunikat o błędnym wyniku. Ktoś może wie, czemu tak się dzieje? Kod: https://pastebin.com/gWydSxHS

#include <iostream>
using namespace std;

int main()
{	
	unsigned int tab[100000];
	unsigned int a;
	cin >> a;
	if (a <= 100000 && a > 0)
	{
		for (int i = 0; i < a; i++)
		{					
			cin >> tab[i];
			if (tab[i] == 1)
				tab[i] = 0;
			else 
			{
				if (tab[i] == 2 || tab[i] == 3 || tab[i] == 5)
					tab[i] = 1;
				else
				{
					if ((tab[i] % 2 != 0) && (tab[i] % 3 != 0) && (tab[i] % 5 != 0))
						tab[i] = 1;
					else tab[i] = 0;
				}				
			}
		}	
		for (int j = 0; j < a; j++)
		{
			if (tab[j] == 1)
				cout << "TAK"<<endl;
			else cout << "NIE" << endl;
		}
	}	
}

 

Answer 1

Zastanów się czy liczba 49 jest liczbą pierwszą i jak widzi ją Twój program...

Answer 2

Przecież liczby pierwsze to nie takie, które są 2, 3, 5 i poza tym, które nie dzielą się przez powyższe, tylko takie, które dzielą się jedynie przez jeden i przez samą siebie, z wyjątkiem jedynki. Poczytaj np. o sicie Eratostenesa.

Comments

Liczby 2,3,5 to tak jakby warunki. Jeśli dana liczba nie dzieli się przez żadne z powyższych to jest ona liczbą pierwszą (czyli dzieli się tylko przez 1 i samą siebie), a jeśli się dzieli przez którąś z powyższych to nie jest ona liczbą pierwszą. Jak pisałem, sprawdzałem to na wiele sposobów i działa- pokazuje dobry wynik, na moim kompilatorze. Także nie rozumiem, czemu na stronie niby nie działa.

Zresztą zachęcam Cię, abyś sam skompilował ten kod i zobaczył czy jest dobry wynik, bo możliwe że moje sposoby okazały się nietrafne.

---

Rzeczywiście, każdą liczbę całkowitą nie będącą pierwszą, poza -1, 0 i 1, można rozłożyć na czynniki 2, 3 lub 5. Tylko twój sposób nie uwzględnia liczb ujemnych. One też przejdą twój test, chociaż pierwszymi nie są.

Jednak są, np. 49, tylko znacznie mniej niż tych z rozkładem na 2, 3 lub 5.

---

Rzeczywiście, każdą liczbę całkowitą nie będącą pierwszą, poza -1, 0 i 1, można rozłożyć na czynniki 2, 3 lub 5

??

Przecież liczb, które nie są pierwszymi i nie mają w rozkładzie 2,3,5 jest nieskończenie wiele... 

---

Liczb całkowitych? Podaj jakiś przykład, bo mi taka nie przychodzi do głowy.

---

49 = 7 * 7

77 = 7 * 11

...

---

No tak, w pośpiechu założyłem, że nie ma takich liczb.

---

"Jednak są, np. 49, tylko znacznie mniej niż tych z rozkładem na 2, 3 lub 5."

To też nie jest prawda. Moc liczb całkowitych jest taka sama jak liczb naturalnych i wynosi aleph zero. Moc zbioru liczb pierwszych też ma taką moc.

---

Oczywiście, chodziło mi bardziej o ich częstość.