Witam
Mam za zadanie napisac algorytm wypisujacy liczby pierwsze z zakresu od 0 do 100. Napisalem cos takiego ale nie doknca mi to dziala. Czy moze mi ktos powiedziec gdzie jest blad?
void main ()
{
int i,j;
const int n=100;
vector <int> pierwsze;
for (i=2; i<=n; ++i)
{
for (j=2; j<=i;++j)
{
if (i%j)
{
pierwsze.push_back(i);
break;
}
}
}
for (int k=0; k=pierwsze.size()-1; k++)
cout <<pierwsze[k]<<endl;
}
sito erastotenesa
albo sito atkina, ktore jest szybsze
Ok. Ale mam wlasnie ich nie uzywac. Sorki ale zapomnialem o tym w tresci napisac.
Więc test Millera-Rabina (test pierwszości).
przyklad petlami:
for(i = 2; i <= 20; i++) {
for(j = 2; j < i && i % j; j++);
if(i == j)
printf("%d\n", i);
}
Z resztą nie wal po całym zakresie a tylko do pierwiastka z maksymalnego zakresu, wystarczy.
Po wielu zmaganiach problem rozwiazalem. Zadanie polegalo na nie stosowaniu roznych sit itp. Oto gotowy kod:
bool czy_pierwsza (int x);
void main ()
{
int i;
bool pierwsza=false;
const int n=100;
vector <int> pierwsze;
for (i=2; i<=n; i++)
{
if (czy_pierwsza(i))
pierwsze.push_back(i);
}
for (int k=0; k<pierwsze.size(); ++k)
cout <<pierwsze[k]<<endl;
}
bool czy_pierwsza (int x)
{
if (x==2 || x==3) //Dodanie do wektora dwoch pierwszych liczb
return true;
if (x==4)
```cpp
//Ominiecie liczby 4 z wektora liczb pierwsze
//gdyz warunkiem ponizszej petli jest x!=2 a warunkiem
//zakonczenia jej przy x=4 byloby dzielenie przez 2
//a jej warunek ja konczy i zwraca true
return false;
int temp = x;
x--;
while (x!=2)
{
if (temp%x)
x--;
else if (!(temp%x))
return false;
}
return true;
}
main powinien być typu int i zwracać 0 przy wykonaniu poprawnie programu.
Zwracanie wartości przez funkcje main jest raczej tylko informacja dla kompilatora ze wszystko jest ok. Jezeli jest to typ void to moze taki pozostac i nie stanowi to problemu. Kompilator z MS VS 2008 i 2010 nie zglasze z tego powodu zadnego bledu. Jedynie przestarzale srodowisko DevC++ cos tam marudzi ale skompilowany program dziala mi na kazdym moim PC.
pastek napisał(a)
Zwracanie wartości przez funkcje main jest raczej tylko informacja dla kompilatora ze wszystko jest ok.
Dla kompilatora? Bzdura.
cout<<"1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97"<<endl;
Wg mnie problemem w tym przypadku jest zrozumienie czym jest liczba pierwsza:
liczba pierwsza
wystarczy zastosować proste dzielenie i stwierdzić czy istnieje reszta z dzielenia...
No wlasnie tak to jest zrobione. Kazda liczba jest wczesniej dzielona modulo przez poprzednia az do 2 gdyz w przypadku liczby parzystej da to wartosc true.
pastek napisał(a)
No wlasnie tak to jest zrobione. Kazda liczba jest wczesniej dzielona modulo przez poprzednia az do 2 gdyz w przypadku liczby parzystej da to wartosc true.
a po co dzielona przez poprzednią?
dziel przez 2 (DWA) - uwzględnij tylko fakt, że dwa jest liczbą pierwszą i po sprawie przecież...
w życiu nie widziałem parzystej liczby pierwszej (oprócz 2 - ofkorz) - jakby co :/
Nie moge dzielic tylko przez 2. Bo np. 4,6,8 itd. podzieli sie modulo przez 2 (DWA) i da wartosc true.
podziel przez dwa
jeśli dostaniesz resztę z dzielenia sprawdź czy dzieli się przez: 3, 5, 7, 9
i po sprawie - tak sądzę...
Kazdy ze sposobow ktory tutaj ja napisalem i Wy piszecie jest ok. Ale skoro juz podalem algorytm i dziala bez zadnych sit tylko na samych petlach to moze zostawmy juz ten problem. Dziekuje wszystkim za wypowiedzi i do nastepnego algorytmu.
pastek napisał(a)
Zwracanie wartości przez funkcje main jest raczej tylko informacja dla kompilatora ze wszystko jest ok. Jezeli jest to typ void to moze taki pozostac i nie stanowi to problemu. Kompilator z MS VS 2008 i 2010 nie zglasze z tego powodu zadnego bledu. Jedynie przestarzale srodowisko DevC++ cos tam marudzi ale skompilowany program dziala mi na kazdym moim PC.
ISO C++ standard ( 3.6.1[2] ) przeczytaj najsampierw co mówi standard potem oceniaj czy jest to poprawnie czy nie. Według standardu NIE JEST to poprawny zapis i fakt, że mingw zawarte w devc++ się pluje jest jak najbardziej na jego korzyść.
Poprawiłem jeszcze algorytm i dodalem mozliwosc wyboru do jakiej liczby ma znajdowac liczby pierwsze.
bool czy_pierwsza (int x);
int main ()
{
int i,n;
bool pierwsza=false;
cout <<"Podaj zakres dla ktorego mam wyswietlic liczby pierwsze: ";
cin >>n;
vector <int> pierwsze;
pierwsze.push_back(2);
for (i=3; i<=n; i+=2)
{
if (czy_pierwsza(i))
pierwsze.push_back(i);
}
for (int k=0; k<pierwsze.size(); ++k)
cout <<pierwsze[k]<<"\t";
}
bool czy_pierwsza (int x)
{
int temp = x;
x--;
while (x!=2)
{
if (temp%x)
x--;
else if (!(temp%x))
return false;
}
return true;
}
Lub inna wersja, która znajduje podana ilosc liczb pierwszych:
bool czy_pierwsza (int x);
int main ()
{
int i,n;
bool pierwsza=false;
cout <<"Podaj ile mam wyswietlic liczb pierwszych: ";
cin >>n;
vector <int> pierwsze;
pierwsze.push_back(2);
for (i=3; ; i+=2)
{
if (czy_pierwsza(i))
pierwsze.push_back(i);
if (pierwsze.size() == n)
break;
}
for (int k=0; k<pierwsze.size(); ++k)
cout <<pierwsze[k]<<"\t";
cout <<endl;
}
bool czy_pierwsza (int x)
{
int temp = x;
x--;
while (x!=2)
{
if (temp%x)
x--;
else if (!(temp%x))
return false;
}
return true;
}
+++++++[>+++++++<-]>[->+>+>+<<<]>>-----<+.>.<+.>.<++.>.>++++++.<.<----..>.<.++.>.<--.>>.<.<.>>++.<.<+.+.>.<-.>>.<.<+.--.>.<++.>>--.<.<+.---.>.<+++.-.>.<+.>>.<.<+.--.>.<++.>>++.<.>---.<<----.>.>.+.<.>.<<.>.>.<<++.>.>.++.<.>-.<<.>.>.+.<.>.--.
Kiedyś pisałem coś podobnego na konkurs jakiś tylko, że "metodą usera Azarien'a" bo chodziło o jak najkrótszy kod ( nie udało się :) ). Dla potomnych kod w bf :)