Dzień dobry, chcę od razu zaznaczyć że poniżej umieszczone polecenie i program służą tylko do celów poszerzenia mojej wiedzy i umiejętności. Nie jest to żadna praca domowa czy zaliczenie.
Polecenie:
Na razie zrobiłem program wyświetlający liczby pierwsze w zakresie 0-100, ale rozszerzenie zakresu to nie problem.
#include
using namespace std;
int main()
{
int max=100;
int licznik=0;
for(int i=1; i
{
for(int j=1; j
{
if(i%j==0)
licznik++;
}
if(i==1 || licznik==1)
{
cout<
}
licznik=0;
}
cout<
system("pause");
}
[/code]
Niestety nie wiem jak się zabrać za polecenie, będę wdzięczny za każdą pomoc która pomoże rozwiązać mój problem.
Zbierz liczby pierwsze do tablicy (i bądź pewny, że jest posortowana wzwyż). Mnożysz przez siebie trzy pierwsze, dodajesz 1 i masz pierwsze n. Powtarzasz procedurę dla liczb z tablicy od drugiej do czwartej. Potem od trzeciej do piątej itd. Wszystko w zgrabnej pętelce.
Poza tym chodzi o liczbę 31 (pierwsza z szukanych), a nie 29.
Co do ogólności problemu (jeśli interesuje nas nie tylko 5 pierwszych, ale może i więcej liczb), to sugeruję lecieć po kolejnych liczbach od 30 i sprawdzać, czy ta dzieli się kolejno przez którąś z liczb pierwszych (wcześniej stablicowanych) - ważne, żeby lecąc po kolejnych liczbach pierwszych brać do dalszego dzielenia nie całą liczbę, a wynik dzielenia. Sprawdzać można do SQRT(n) (pierwiastek z liczby n). Trzecie dzielenie (bez reszty) powinno dać 1 - wtedy wypisujemy bazową liczbę (n+1). Algorytm może nie najefektywniejszy, ale prosty i szybki.
Pablo ma w większości rację, choć z jednym się nie zgodzę do końca.
Pierwszą szukana liczba jest 31.
Generalnie należy zapisać wszystkie liczby pierwsze do pewnej wartości 2, 3, 5, 7, 11, 13, …
Z własności iloczynu wiemy, że pierwszą szukana liczbą będzie {2 * 3 * 5} + 1, przy czym w nawiasach wąsatych mamy nasze n - 1, stąd należy 1 dodać.
Lepszy algorytm będzie polegał na tym, że następnym iloczynem z braku wyboru będzie 2 * 3 * 7, następny 2 * 5 * 7 albo 2 * 3 * 11 wszystkie inne będą większe. Innymi słowy musimy zrobić 5 pointerów (albo indeksery). W ogólnym przypadku iloczyn naszej liczby składa się z a * b * c i ap, bp, cp wskazują na indeksy + 2 wskazujące na lower-bound w b i c. Sprawdzamy czy dałoby się przesunąć ap na następną pozycję jeśli nie ma pointera od b to patrzymy jaka liczbę dostaniemy w wyniku podmiany jednego z czynników, analogicznie dla b, a dla c po prostu next, bo nie ma blokady. Z tych 5 możliwości bierzemy min i przesuwamy odpowiedni pointer. Jeśli l-b zrówna się pointerem rozważamy tylko pointer (lower-bound nie może przekroczyć pointera). Przykładowo właśnie po 2 * 3 * 11, będzie 2 * 5 * 7, w sumie trochę pogmatwałem, jeśli autor potrzebuje mogę to wyspecyfikować w punktach.
– Dodane 25.01.2013 (Pt) 18:14 –
@[alex]
Mylisz się trzecia będzie 2 * 3 * 11 + 1 = 67, u ciebie 71.