Potrzebuję algorytmu znajdującego 20 pierwszych par liczb bliźniaczych i pomysłu na obliczenie jego złożoności symptotycznej \(\displaystyle{ O()}\)(duże O)
Liczby bliźnicze p i q to takie liczby że:
\(\displaystyle{ q=p+2}\)
Algorytm - liczby bliźniacze
-
- Użytkownik
- Posty: 222
- Rejestracja: 24 sie 2009, o 02:21
- Płeć: Mężczyzna
- Lokalizacja: Katowice
- Pomógł: 32 razy
Algorytm - liczby bliźniacze
Szukaj kolejnych liczb pierwszych, a następnie wśród liczb pierwszych szukaj liczb bliźniaczych. Do wyszukiwania liczb pierwszych możesz użyć sita Eratostenesa.
- Adatiel
- Użytkownik
- Posty: 96
- Rejestracja: 14 sie 2008, o 15:20
- Płeć: Mężczyzna
- Lokalizacja: czaplinek
- Podziękował: 2 razy
Algorytm - liczby bliźniacze
Oto algorytm - mógłbym prosić o pomysł na obliczenie O()?
Kod: Zaznacz cały
#include <iostream.h>
using namespace std;
int main()
{
cout << "Liczby blizniacze
";
int n;
n=320;
n++;
bool tablica[n];
for(int i = 2; i < n; i++)
tablica[i] = true;
for(int i = 2; i < n; i++)
for(int l = i+1; l < n; l++)
if(l % i == 0)
{
tablica[l] = false;
}
for(int i = 0; i < n;i++)
for(int l = 0;l < n; l++)
if(tablica[i] == true && tablica[l] == true)
if(i - l == 2)
cout << i << " " << l << endl;
system("pause");
return 0;
}
Ostatnio zmieniony 8 wrz 2010, o 17:11 przez Anonymous, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- Użytkownik
- Posty: 222
- Rejestracja: 24 sie 2009, o 02:21
- Płeć: Mężczyzna
- Lokalizacja: Katowice
- Pomógł: 32 razy
Algorytm - liczby bliźniacze
Na oko \(\displaystyle{ \Theta( n^2)}\), ze względu na zagnieżdżone pętle. Formatuj kod, bo w przeciwnym przypadku ciężko się go czyta. Można to samo zrobić w \(\displaystyle{ \Theta(n \log(n) )}\) implementując wspomniane wcześniej sito.