Forum Programowanie c++, delphi Ostatnio aktywny: Nigdy
Nie zalogowany [Zaloguj ]
Pokaż koniec
Wersja do druku | Zapisz | Dodaj do Ulubionych   Wyślij nową wiadomość Sonda:
Autor: Temat: Liczby pierwsze
Ast3rot
Member
**


Avatar


Postów: 92
Zarejestrowano: 24-12-2005
Miasto: Konin
Offline

Nastrój: zmęczony byciem

[*] wysłano w 26-4-2006 o godz. 10:32 Odpowiedz cytując
Liczby pierwsze



Ma ktos pomysł na to http://opss.safo.biz/?menu=comp&sub=prob&comp=0&prob=1004 zadanie?

Moj algorytm tworzy tablice z n liczbami pierwszymi gdzie n jest najwieksza liczba zestawu, ale przy drugiem tescie wymieka z powodu limitu pamieci

nie wiem czy sie przyda ale wkleje moj kod:
Kod:

#include <iostream>
using namespace std;

int main() {
int n, *wsk,*wyn,m=0,x,naj;
cin>>x;
int wyniki[x];
wyn = new int[x];
bool fir;
for(int a=0;a<x;a++) {
cin>>n;
wyniki[a]=n;
}
naj=wyniki[0];
for(int i=1;i<x;i++){
if(naj<wyniki)
naj=wyniki;
}
wsk = new int[naj];
wsk[0]=2;
for(int i=3;m<naj;) {
fir=1;
for(int j=0; j<m+1; j++){
if(i%wsk[j]==0){
fir=0;
break;
}
}
if(fir){
wsk[m+1]=i;
m++;
}
i++;
}
for(int i=0;i<x;i++)
cout<<wsk[wyniki-1]<<endl;
}//;~


[Wyedytowany dnia 26-4-2006 > Ast3rot]




Pokaż profil użytkownika E-Mail Użytkownika Pokaż wszystkie wiadomości użytkownika Użytkownik U2U Ten użytkownik posiada komunikator Gadu-Gadu
__max
Member
**




Postów: 35
Zarejestrowano: 24-1-2006
Miasto: Lublin
Offline

Nastrój: niezdefiniowany.... :|

[*] wysłano w 26-4-2006 o godz. 16:40 Odpowiedz cytując


Szukaj liczby pierwsze sitem Eratostenesa - jest to bardzo szybki sposób znajdowania liczb pierwszych, zżera trochę pamięci, ale i tak spokojnie powinieneś się zmieścić w limicie i to ze sporym zapasem, bo piętnastotysięczna liczba pierwsza nie jest jeszcze taka duża...
Żeby zmniejszyć zużycie pamięci możesz skorzystać z klasy bitset z STL-a (nagłówek <bitset> - tylko nie wiem, czy użycie klas STL jest w OPSS dozwolone), ale to już raczej dla własnej satysfakcji, bo do zaliczenia testów pamięci i tak wystarczy.
Powodzenia

[Wyedytowany dnia 26-4-2006 > __max]
Pokaż profil użytkownika Pokaż wszystkie wiadomości użytkownika Użytkownik U2U Ten użytkownik posiada komunikator Gadu-Gadu
MitS
Top Coder
***


Avatar


Postów: 384
Zarejestrowano: 1-1-2006
Miasto: Olsztyn
Offline

Nastrój: Uhahany

[*] wysłano w 27-4-2006 o godz. 06:15 Odpowiedz cytując


ja to zrobiłem tak:


Kod:

#include <iostream>

using namespace std;

int main()
{
int a, b, c;
cin >> c;
for (a=2; a<(c+1); a++)
{
for (b=2; b<(a+1); b++)
{
if (a%b==0)
{
if (a!=b)
{
b=a+1;
}
else
{
cout << a << endl;
}
}
}
}
cout << endl;
return 0;
}



... ale nie wywala błąd na pierwszym teście :/




Pokaż profil użytkownika E-Mail Użytkownika Pokaż wszystkie wiadomości użytkownika Użytkownik U2U MitS's Aim Ten użytkownik posiada komunikator Gadu-Gadu
faxe
Coder
***


Avatar


Postów: 130
Zarejestrowano: 17-12-2005
Miasto: Gdynia
Offline

Nastrój: czarna rozpacz

[*] wysłano w 27-4-2006 o godz. 07:46 Odpowiedz cytując


mits, *T*a metoda jest chyba najwolniejsza z mozliwych [:

Nawet gdy zakres dzielników zawęzić do 2-sqrt(a) to będzie wolniejsza od sita Era-kogośtam

[Wyedytowany dnia 2006-4-27 > faxe]




Pokaż profil użytkownika Pokaż wszystkie wiadomości użytkownika Użytkownik U2U faxe's Aim Ten użytkownik posiada komunikator Gadu-Gadu faxe's Yahoo
MitS
Top Coder
***


Avatar


Postów: 384
Zarejestrowano: 1-1-2006
Miasto: Olsztyn
Offline

Nastrój: Uhahany

[*] wysłano w 27-4-2006 o godz. 12:14 Odpowiedz cytując


Cytuj

mits, ma metoda jest chyba najwolniejsza z mozliwych [:


dobrze :] ale nie chodzi mi o szybkość tylko pytanie czemu nie działa :]
Czemu to wiem, a jak to usprawnić :> ??




Pokaż profil użytkownika E-Mail Użytkownika Pokaż wszystkie wiadomości użytkownika Użytkownik U2U MitS's Aim Ten użytkownik posiada komunikator Gadu-Gadu
faxe
Coder
***


Avatar


Postów: 130
Zarejestrowano: 17-12-2005
Miasto: Gdynia
Offline

Nastrój: czarna rozpacz

[*] wysłano w 27-4-2006 o godz. 17:16 Odpowiedz cytując


Cytuj

Czemu to wiem, a jak to usprawnić :> ??


zamiast tego:

b<(a+1);

dodaj zmienną "int pierw", przypisz jej "sqrt(a)" i podmien powyzszy kod na:

b<=pierw;




Pokaż profil użytkownika Pokaż wszystkie wiadomości użytkownika Użytkownik U2U faxe's Aim Ten użytkownik posiada komunikator Gadu-Gadu faxe's Yahoo
Ast3rot
Member
**


Avatar


Postów: 92
Zarejestrowano: 24-12-2005
Miasto: Konin
Offline

Nastrój: zmęczony byciem

[*] wysłano w 29-4-2006 o godz. 13:12 Odpowiedz cytując


czas[s] pamiec[kB] rozmiar[B]
Program zaakceptowany C++ 0.31 264 440

utworzylem tablice z 15 000 pierwszych liczb pierwszych a pozniej pobralem ilosc zestawow i od razu dla kazdej liczby z zestawu wyrzucalem odpowiadajaca jej liczbe pierwsza z tablicy
(:




Pokaż profil użytkownika E-Mail Użytkownika Pokaż wszystkie wiadomości użytkownika Użytkownik U2U Ten użytkownik posiada komunikator Gadu-Gadu
__max
Member
**




Postów: 35
Zarejestrowano: 24-1-2006
Miasto: Lublin
Offline

Nastrój: niezdefiniowany.... :|

[*] wysłano w 30-4-2006 o godz. 20:58 Odpowiedz cytując


Trochę łopatologicznie, ale ja to zrobiłem tak samo ;)
Pokaż profil użytkownika Pokaż wszystkie wiadomości użytkownika Użytkownik U2U Ten użytkownik posiada komunikator Gadu-Gadu
Wyślij nową wiadomość Sonda:


Pokaż początek

Sitemap
Copyright © 2005-2007 by coding-portal.com
Programowaniedla każdego. Programowanie w c++, java, delphi, pascal, perl oraz innych językach. Tworzenie stron w html, xhtml, php z użyciem mysql, css oraz ich pozycjonowanie. Zapraszamy do udziału w życiu naszego forum!
[zapytań: 15]
[PHP: 91.1% - SQL: 8.9%]