Liczby Mersenne'a [C].

[toomek93 0]

Zadanie jest następujące.

 

Liczba Mersenne'a to liczba pierwsza postaci 2^p −1, gdzie p jest liczbą 

pierwszą. Napisać program, który znajduje liczby Mersenne'a z przedziału 

< a,b > zdefiniowanego przez użytkownika. Program powinien zawierać funkcje: 

• sprawdzającą, czy podana liczba jest liczbą pierwszą; 

• wyznaczającą n-tą liczbę Mersenne’a. 

Zapewnić poprawność wprowadzonych danych.

 

Zadanie nie jest chyba trudne. Funkcję na sprawdzanie czy liczba jest liczbą pierwszą dam spokojnie radę napisać ale tą drugą z liczbami Mersenne'a już nie. Mógłby ktoś pomóc?

[Malwin 16]

Zadanie banalne :

 

1) Najpierw rozwiązujesz dwa równania postaci 2^p - 1 = a oraz 2^p - 1 = b. To pomoże określić przedział, z których trzeba wybrać liczby pierwsze. (Oczywiście wynikiem tych równań możę być liczba rzeczywista wtedy trzeba odpowiednio zaokrąglić). Mając ten przedział znajdujesz w nim liczby pierwsze. Mając liczby pierwsze podstawiając do 2^p -1 wyliczysz kolejne liczby Mersenne'a

[toomek93 0]

A coś dokładniej byś mógł?

[Malwin 16]

Najwięszkym problemem dla Ciebie będzie pewnie rozwiązanie równań. Dlatego podpowiedź :

 

Logartym o podstawie a z b to to samo co logartym o podstawie c z b przez logartym o podstawie c z a. No chyba, że możesz użyć jakieś zewnętrznej bilbioteki do c, gdzie bez problemu można liczyć logartym z liczb o podstanej postawie. Bo w bibliotece standardowej jest chyba tylko o podstawie 10 i e. Dlatego podpowiedź powinna ułatwić zadanie.

[toomek93 0]

I tak nie ogarniam. Najlepiej jakby ktoś to po prostu napisał ale wątpię że ktoś taki się znajdzie więc posiedzę z tym, może coś mi się z czasem wyjaśni.

[Malwin 16]

c = log(a - 1) / log(2);
d = log(b - 1) / log(2);

Potem to odpowiednio zaokręglij do liczb całkowitych. c w dół d w górę. Od tego też są funkcje.

Edytowane 3 Marca 2013 przez Malwin

[toomek93 0]

Stary napisz ten program bo ja już nie wiem. Wgl nie rozumiem tego zadania. Po co mi tam wgl liczby pierwsze skoro od razu mogę wyznaczyć liczby Mersenne'a z tego przedziału?

Edytowane 3 Marca 2013 przez toomek93

[Malwin 16]

Jak je wyznaczysz bez liczb pierwszych. Liczba Mersenne'a to 2^p - 1 gdzie p jest właśnie liczbą pierwsza. Więc nie możesz sobie za p podstawiać kolejnych liczb naturalnych 1,2,3,4,5 itd tylko muszą to być liczby pierwsze 2,3,5 itd.

 

Gdyby przedział <a,b> dotyczył zmiennej p to prosta sprawa. Masz przedział a,b wyznaczasz z niego liczby pierwsze i wyznaczone liczby podstawiasz do wzoru p^2 - 1. Ale neistety tutaj przedział a,b to już same liczby Mersenne'a nie p. Więc jakbyś to chciał inaczej zrobić niż zaproponowałem? Wyznaczał po kolei liczby Mersenne'a sprawdzał czy i sprawdzał które mieszczą się w przedziale? Dla przedziału, który zaczyna się od wysokiej liczby było by to przecież strasznie nieoptymalne, aczkolwiek by działało...

 

Taka rada :

 

1) Zrozumieć zadanie

2) Porafić rozwiązać je na kartce

3) Dopiero brać się za jakąkolwiek implementacje

4) Ewentualne poprawki ( często się zdarza, że gdzieś zamiast >= jest samo > itp)

 

Jednak jak chcesz, żeby to tylko działało to :

 

W pętli liczysz 2^p-1 dla kolejnych liczb pierwszych zaczynając od 2. Algorytm na liczby pierwsze znajdziesz na wiki chociażby używając sita. Dla każdej liczby Mersenne'a sprawdzasz czy jest z przedziału a,b jeśli tak zapamiętujesz w tablicy. Jak liczba Mersenne'a jest większa niż b to kończysz. W tablicy wtedy masz wszystkie liczby Mersenne'a z przedziału a,b.

 

Co do wyznaczenia n-tej liczby Mersenne'a to wystarczy zauważyć, że n-ta liczbę można obliczyć mając n-tą liczbę pierwszą.

 

Tak więc 5-ta liczba Mersenne'a to 2^11 - 1 bo 11 to 5-ta liczba pierwsza : 2, 3, 5, 7, 11

Edytowane 3 Marca 2013 przez Malwin

[toomek93 0]

Nie, dobra koniec, odpadam. Nie ogarnę tego jak nie zobaczę gotowego kodu.

Edytowane 3 Marca 2013 przez toomek93

[Malwin 16]

A przedział <a,b> to nie są zwykłe liczby? Ja to widzę tak: definiuje przedział, znajduję w nim liczby pierwsze p, a potem liczby Mersenne'a. To moja wizja ale kompletnie nie wiem jak to napisać.

 

Jak dla mnie z pierwszego posta jasno wynika, że z przedziału <a,b> znaleźć liczby Mersenne'a. Przykład łopatologiczny.

 

Masz przedział <1,50> i z niego znaleźć liczby Mersenne'a :

Algorytmem sita znajduje liczby pierwsze z ww. przedziału 2,3,5,7,11,...,47

Kolejno podstawiam te liczby pierwsze do 2^p - 1 i sprawdzam czy wynik jest z przedziału a,b.

Jeśli jest z tego przedziału to zapamiętuje + jak jest więszky od b to kończę.

 

Jest to nie optymalne, ale działa bo widzisz, że znajdujesz dużo liczb pierwszych, a defakto z tego tylko kilka pierwszych pasuje.

[toomek93 0]

Nie dam rady, dla mnie to kompletnie czarna magia. Może i rozumiem sens zadania ale kompletnie nie potrafie przełożyc go na język C.

[Malwin 16]

Ja nie będę pisał gotowca tym bardziej do zadań tego typu. To są zadania, które mają na celu nauczenie myślenia i algorytmów. Jeśli chcesz gotowca to tego jest na pęczki w google'ach.

 

Nie wiem co w tym trudnego pętle for, tablica, oraz wykorzystanie funkcji pow lub przesunięcia bitowego do potęgowania. Ja ze swej strony służyłem dobrą radą, wytłumaczeniem i zrozumieniem samego zadania.

Edytowane 3 Marca 2013 przez Malwin

[szatkus 282]

int func2(int n) {
  if (n <= 0) {
    return -1;
  }
  int numbersFound = 0;
  int base = 4;
  int p = 2;
  while (p < 32) {
    if (func1(base - 1)) {
      numbersFound++;
      if (numbersFound == n) {
        return base - 1;
      }
    }
    base *= 2;
    p++;
  }
  return -1;
}

 

Tak żeby uciąć zbędne dyskusje.

[toomek93 0]

 

int func2(int n) {
  if (n <= 0) {
    return -1;
  }
  int numbersFound = 0;
  int base = 4;
  int p = 2;
  while (p < 32) {
    if (func1(base - 1)) {
      numbersFound++;
      if (numbersFound == n) {
        return base - 1;
      }
    }
    base *= 2;
    p++;
  }
  return -1;
}

 

Tak żeby uciąć zbędne dyskusje.

A co to jest func1?

Dobra, teraz inne pytanie. Znalazłem sposób jak wyszukiwać liczby pierwsze (nie w funkcji bo nie potrafię jej napisać ale jest). Teraz mam problem jak wpleść w to funkcję którą napisał szaktus aby program wyszukiwał liczby Mersenne'a. Oto co napisałem:

unsigned long i,j,n, p,pierw, ilosc;

int main(void)
{
	printf("Podaj gorny zakres: ");
	scanf("%d", &n);

	pierw = sqrt(n)+1;
	unsigned long T[pierw];
	unsigned long THigh = 0;
	T[0] = 2;

	if (n>=2) printf("2\t");

	for (i=3; i<=n; i+=2) {
		p = sqrt(i)+1;
		for (j=1; (j<=THigh) && ((i%T[j])!=0) && (T[j]<=p); j++);
		if ((j>THigh)||(T[j]>=p)) {
			ilosc++;
			printf("%d\t", i);
			if (i <= pierw) T[++THigh]=i;
		}
	}

	printf("\nIlosc liczb pierwszych : %d\n\n", ilosc);
	return 0;
}
 

 

 

 

[szatkus 282]

 

A co to jest func1?

 

Zapomniałem dopisać, func1 to funkcja z pierwszej kropki (czyli określająca czy liczba jest pierwsza). Teraz tylko wyciągnij fragment sprawdzający pierwszość i ubierz go w funkcję.