Witam wszystkich, pisałem już program do sprawdzania czy liczba jest pierwsza, lecz nie mam kompletnie pojęcia w jaki sposób się do tego zabrać czy mogli byście coś mi podpowiedzieć ?
0
1
Podstawowe pytanie w tego typu przypadkach - ustalmy, czego nie rozumiesz.
Czy umiałbyś to sobie zrobić ręcznie/na kartce, ale nie wiesz, jak to przełożyć na program, czy w ogóle nie łapiesz, o co chodzi? ;)
0
Wydaje mi się ze potrafię zrobić to na kartce, ale kompletnie nie wiem jak to przepisać w program, moim zdaniem powinno to być mniej więcej tak:
zakres liczb od 2 do 5000, podaję liczbę, do tablicy mam wpisane wszystkie liczby pierwsze, z sita Eratostenesa, jeśli liczba jest pierwsza to z tablic porównuję tę liczbę, którą wprowadziłem z klawiatury, z liczbami pierwszymi z tablicy, i wyświetla mi że jest to liczba pierwsza i jest np 5 w kolejności
0
tablicy mam wpisane wszystkie liczby pierwsze
A te liczby masz wpisane na sztywno, czy najpierw musisz je obliczyć?
Natomiast co do zasady - z grubsza to chyba Twoja wizja jest OK :)
0
myślę, że powinny być wyliczane za każdym razem za pomocą algorytmu Eratostenesa
Na tę chwilę mam tylko takie coś :/ bo kodem to chyba tego nie można nazwać :D
#include<iostream>
#include<cstdlib>
using namespace std;
bool czy_pierwsza(int n)
{
if(n<2)
return false;
for(int p=2;p*p<=n;p++)
if(n%p==0)
return false;
return true;
}
int main()
{
int n,X;
cout<<"Podaj liczbe do sprawdzenia: ";
cin>>n;
if(czy_pierwsza(n))
cout<<"Liczba: "<<n<<" jest pierwsza oraz jest "<<X<<" w kolei ";
else
cout<<"Liczba: "<<n<<" nie jest pierwsza";
return 0;
}
0
No to masz pierwszy krok, który musisz ogarnąć - napisz program, który po uruchomieniu zapełnia tablicę liczbami pierwszymi z danego przedziału. Jak to ogarniesz, to będziemy kombinować dalej ;)
0
Coś takiego zapisuje mi w " i " wszysktkie wartości do liczby którą podam, powinno być tak? Czy wszystkie od 2 do 5000
#include <iostream>
using namespace std;
bool tab[5000];
int main()
{
int n;
cin>>n;
cout<<endl;
for(int i=2; i*i<=n; i++)
{
if(tab[i]==true)
continue;
else{
for(int j=2*i; j<=n; j=j+i)
{
tab[j]=true;
}
}
}
for(int i=2; i<=n; i++)
{
if(tab[i]==false)
{
cout<<i<<endl;
}
}
return 0;
}
0
Chyba że ma zapisać od razu wszystkie
Właśnie chciałem to napisać - Ty pytasz użytkownika o liczbę (znaczy - czekasz na wprowdzenie czegoś, ale nie ma żadnego komunikatu. To też by wypadało poprawić i dodać jakiś tekst w stylu "Podaj liczbę z zakresu 2-5000 do sprawdzenia), ale moim zdaniem tablica powinna być zapełniona dla całego zakresu, a nie jedynie 2-podana liczba. Jeśli np. będziesz chciał dodać możliwość wielokrotnego sprawdzenia, to lepszą opcją jest raz wygenerować tablicę z liczbami, a potem jej nie ruszać, a jedynie odczytywać jej zawartość.
0
No okej, czyli mam ten kod, i za nic nie wiem jak to dalej zrealizować w sensie, wypisuje mi do tablicy wszystkie liczby pierwsze od 2 do 5000, teraz muszę dodać do tego liczbę wprowadzaną przez użytkownika, program mam sprawdzić czy ta liczba znajduje sie w tablicy, jeśli tak to wyświetlić tak jest to liczba n(pierwsza) oraz napisać która z kolei, i teraz nie mam pojęcia co dalej jak to zrealizować, wystarczy jednokrotny wybór
#include <iostream>
using namespace std;
bool tab[5000];
int main()
{
int n;
n=5000;
for(int i=2; i*i<=n; i++)
{
if(tab[i]==true)
continue;
else{
for(int j=2*i; j<=n; j=j+i)
{
tab[j]=true;
}
}
}
for(int i=2; i<=n; i++)
{
if(tab[i]==false)
{
cout<<i<<endl;
}
}
return 0;
}
0
Tego drugiego for możesz wywalić - realizuje on coś, co nam jest niepotrzebne, czyli wypisuje wszystkie liczby pierwsze z danego przedziału. Zamiast tego daj kod, który sprawdzi, czy podana liczba jest liczbą pierwszą i wyświetli napis "TAK" albo "NIE". Wiesz, jak to zrobić?
0
Nie za bardzo, mam napisany program sprawdzający czy liczba jest pierwsza i wyświetlający tak lub nie, lecz nie wiem jak je połączyć
0
A zastanów się - w jaki sposób ma się wykonać sprawdzenie liczb pierwszych w oparciu o istniejącą tablicę? Abstrahując od algorytmu/programowania - jak "tak po ludzku" byś chciał to zrobić? Powiedzmy, że masz wydrukowaną tabelkę z liczbami pierwszymi i chcesz sprawdzić (opierając się o tą tabelkę), czy dana liczba jest pierwsza.
0
Myślę ze wartość n bym == do jakiejś wartości z tabeli ale ja naprawdę zaczynam i kompletnie nie mam bladego pojęcia
0
Dokładnie tak :)
Skoro masz tabelę 2-5000, czyli każda liczba z podanego przedziału ma przypisaną wartość TRUE/FALSE, to sprawdzenie czy jest pierwszą sprowadza się do odczytania, jaką wartość posiada tabela pod zadanym indeksem. Myślę, że teraz wiesz, co masz zrobić.
0
Niby wiem co mam zrobić ale nie wiem jak to zrobić hmm, skleiłem coś takiego i nie działa a nie bardzo widzę błąd
#include <iostream>
using namespace std;
bool tab[5000];
int main()
{
int n,m;
n=5000;
for(int i=2; i*i<=n; i++)
{
if(tab[i]==true)
continue;
else{
for(int j=2*i; j<=n; j=j+i)
{
tab[j]=true;
}
}
}
cout << "Podaj liczbę do sprawdzenia";
cin >>m;{
for (int m = 0; !tab && m < 2; ++m)
tab = (m == tab[i]);
{
if (tab)
cout << "Jest w tablicy" << endl;
else{
cout << "Nie ma w tablicy" << endl;
}}}
return 0;
}
0
mam taki kod, lecz nie wiem co dalej. Mój algorytm nie sprawdza czy w ogóle taka wartość jest w tablicy czy nie, a ja muszę zrobić aby jeszcze pokazało, która jest w kolejności. A nie potrafię nawet sprawdzić w tablicy.
#include <iostream>
using namespace std;
bool tab[5000];
int main()
{
int n,m;
n=5000;
for(int i=2; i*i<=n; i++)
{
if(tab[i]==true)
continue;
else{
for(int j=2*i; j<=n; j=j+i)
{
tab[j]=true;
}
}
}
cout << "Podaj liczbę do sprawdzenia";
cin >>m;{
for (int m = 0; !tab && m < 2; ++m)
tab = (m == tab[i]);
{
if (tab)
cout << "Jest w tablicy" << endl;
else{
cout << "Nie ma w tablicy" << endl;
}}}
return 0;
}
0
Każda liczba w tablicy ma swój indeks, a pod nim zapisaną wartość TRUE/FALSE. Ty umiesz odczytać wartość danego elementu tablicy (podpowiedź: wykorzystujesz to w pierwszej pętli for - linia 14). Drugi for (linie 26-27) jest niepotrzebny, sprawdzenie zrób analogicznie do linii numer 14.
0
cerrato napisał(a):
Każda liczba w tablicy ma swój indeks, a pod nim zapisaną wartość
TRUE/FALSE. Ty umiesz odczytać wartość danego elementu tablicy (podpowiedź: wykorzystujesz to w pierwszej pętlifor- linia 14). Drugi for (linie 26-27) jest niepotrzebny, sprawdzenie zrób analogicznie do linii numer 14.
Ale czy wtedy będę w stanie sprawdzić która to jest liczba z kolei ? Naprawdę nie mam pojęcia jak do tego podejść
#include <iostream>
using namespace std;
bool tab[5000];
int main()
{
int n,m;
n=5000;
for(int i=2; i*i<=n; i++)
{
if(tab[i]==true)
continue;
else{
for(int j=2*i; j<=n; j=j+i)
{
tab[j]=true;
}
}
}
cout << "Podaj liczbe do sprawdzenia: ";
cin >>m;
for(int i=2; i<=n; i++)
{
if(tab[i] == m )
cout << "Jest "<<endl;
else{
cout << "nie jest w tablicy"<<endl;
}
}
return 0;
}
0
Czy ten kod uruchomiłeś u siebie? Bo u mnie po podaniu liczby (ja akurat wpisałem 25, ale nie ma to większego znaczenia) dostałem na ekranie pełno komunikatów. A liczyłem na to, żeby pojawiła się jedna i tylko jedna informacja o tym, czy jest, czy nie pierwsza.
P.S. zmieniłbym komunikat z "nie ma w tablicy" na "jest/nie jest liczbą pierwszą". Z punktu widzenia użytkownika, program nie ma sprawdzać w tablicy, ale ma określić, czy dana liczba jest pierwsza.
1
Sprawdzasz bezpośrednio, o to chodzi, żeby nie było pętli - sprawdzenie mamy w czasie stałym. Napiszę Ci to, bo chyba Masz blind spot:)
int m;
cin >> m;
if (m == 0 || m == 1)
cout << "Nie\n";
else {
if (!tab[m])
cout << "Tak\n";
else
cout << "Nie\n";
}
Wcześniej trzeba też załatwić 0 i 1, gdyż tu tablica daje błędny wynik.
W ten sposób, mamy tylko sprawdzenie czy liczba jest pierwsza, jeśli potrzebna będzie kolejność, to iteracja jest konieczna; albo wcześniej stworzyć tablice liczb pierwszych i na niej szukanie liniowe.
0
lion137 napisał(a):
Sprawdzasz bezpośrednio, o to chodzi, żeby nie było pętli - sprawdzenie mamy w czasie stałym. Napiszę Ci to, bo chyba Masz blind spot:)
int m; cin >> m; if (m == 0 || m == 1) cout << "Nie\n"; else { if (!tab[m]) cout << "Tak\n"; else cout << "Nie\n"; }Wcześniej trzeba też załatwić
0i1, gdyż tu tablica daje błędny wynik.
W ten sposób, mamy tylko sprawdzenie czy liczba jest pierwsza, jeśli potrzebna będzie kolejność, to iteracja jest konieczna; albo wcześniej stworzyć tablice liczb pierwszych i na niej szukanie liniowe.
Bardzo dziękuję Ci za pomoc, i to dość sporo mi rozjaśniło, lecz niestety nadal nie potrafię sprawdzić, którą z kolei liczbą pierwszą jest ta wprowadzona z klawiatury
0
nadal nie potrafię sprawdzić, którą z kolei liczbą pierwszą jest ta wprowadzona z klawiatury
Skoro umiesz sprawdzić, czy OKREŚLONA liczba jest liczbą pierwszą, to żeby uzyskać jej numer/kolejność/pozycję, musisz w pętli for przelecieć przez tablicę i za każdym razem, jeśli liczba (z przedziału od 2 do WybranaLiczba - 1) jest pierwsza, zwiększasz ilość. Na końcu ilość liczb przed Twoją, powiększona o 1 da Ci pozycję podanej przez użytkownika liczby.
0
Tak, dokładnie taki patern Masz zastosować, "wyszukiwanie liniowe", jak napisał @cerrato , tylko, ja bym to z dydaktycznych względów uprościł, wyszukiwał we wcześniej utworzonej i zapisanej tablicy liczb pierwszych mniejszych od n. Skomentowałem zmiany w kodzie:
bool tab[5000];
int p[1000]; // dodana tablica na liczby pierwsze. do
// 5000 wystarczy 1000 =20%, a jest około 10%
int main() {
int n;
n=5000;
int sz = 0; // rozmiar tablicy z liczbami pierwszymi
for(int i=2; i*i<=n; i++)
{
if(tab[i]==true)
continue;
else{
for(int j=2*i; j<=n; j=j+i)
{
tab[j]=true;
}
}
}
for(int i=2, /* dodalem j*/j = 0; i<=n; i++)
{
if(tab[i]==false)
{
p[j] = i; // wpisanie liczby pierwszej do tablicy
++j; // inkrementacja j
++sz; // inkrementacja tego rozmiaru
}
}
int m;
cout << "Podaj liczbe do sprawdzenia: ";
cin >> m;
if (m == 0 || m == 1)
cout << "0 i 1 nie sa pierwsze\n";
else {
// "linear search pattern:"
int i = 0;
while ( i < sz) {
if (m == p[i]) {
cout << "podana liczba= "<<m <<" jest " <<i + 1 <<" w kolejnosci liczb pierwszych\n";
// i + 1, bo array indexes start at 0:)
break;
}
++i;
}
if (i == sz) // jeśli iterator (indeks) znajduje sie na koncu tablicy, to nie znalezlismy
cout << "podana liczba= " <<m<<" nie jest liczba pierwsza\n";
}
cout << "\n";
return 0;
}
0
Czy mógłbyś mi wytłumaczyć jeszcze linijkę 7, oraz 26,27 ?
0
Na początku sz = 0, gdyż nie mamy jeszcze żadnej liczby pierwszej, potem za każdym razem, jak dodajemy liczbę pierwszą do tablicy (linia 25), to również inkrementujemy jej rozmiar (linia 27); co do linii 26, ten drugi indeks pętli, j musi być inkrementowany tylko gdy mamy kolejną liczbę pierwszą, inaczej będzie bug. W efekcie dostajemy tablicę p, w której do indeksu sz - 1, mamy wszystkie, kolejne i tylko takie, liczby pierwsze mniejsze lub równe n. Możesz zresztą tę tablice wydrukować.