Błędy w programie znajdowania liczb pierwszych
Ostatnio zmodyfikowano 2016-12-06 11:09
Numb3r Temat założony przez niniejszego użytkownika |
Błędy w programie znajdowania liczb pierwszych » 2016-12-03 12:31:38 Program ma gdzieś błąd, co podaje sprawdzarka i przekracza limit czasu. Nie wiem, jak go poprawić.
#include <iostream> using namespace std; int main(){ int n, b; cin>>n; long long T[n]; for (int i=0; i<n; i++) cin>>T; for (int c=0; c<n; c++) { if (T[c]<=1); else if (T[c]==2) cout<<T[c]<<endl; else { for(int a=1;a*a<=T[c];a++){ b=0; if (T[c]%a) b=b+1; } if(b==1) cout<<T[c]<<endl; } } } |
|
dakruzz |
» 2016-12-05 23:05:15 [ cpp ] Twój kod [ /cpp ] - uzyj tego nastepnym razem. Przeanalizuj mój kod, bo Twój to straszny syf i ciężko się ogarnąć w nim. #include <iostream>
using namespace std;
int main() { int n, i; cout << "podaj liczbe: "; cin >> n; if( n % 2 != 0 ) { cout << n << " jest nieparzyste" << endl; for( i = 2; i < n; i++ ) { if( n % i == 0 ) { cout << "Liczba nie pierwsza"; return 0; } else { } } cout << "Liczba pierwsza"; } else { cout << "Liczba parzysta"; } return 0; }
|
|
Gibas11 |
» 2016-12-05 23:35:15 @UP Jak już to for( i = 2; i < std::sqrt( n ); i++ ) , chociaż to i tak skrajnie nieefektywne rozwiązanie. |
|
dakruzz |
» 2016-12-05 23:42:16 Ja wiem, ja wiem, ale wtedy jeszcze nie wiedziałem( a nawet nie mogłem używać) o innych sposobach. Myślę, że lepiej dla takiej osoby jak On podać w miarę prosty i zrozumiały kod. Wiem, bo sam jestem świeży |
|
Gibas11 |
» 2016-12-05 23:54:24 Dlatego nie zarzucałem linkami do wikipedii z opisami wymyślnych testów pierwszości, tylko tą drobną poprawką, która i tak robi ogromną różnicę w wydajności, zwłaszcza dla dużych liczb. Np. w wypadku sprawdzania 60'000 (pomijając oczywistość wyniku), zamiast 59'998 iteracji i dzieleń wystarczą 244. //edit: I uwzględniając to co już jest w tym kodzie, najlepszym prymitywnym rozwiązaniem jest for( i = 3; i < std::sqrt( n ) + 1; i += 2 ) , chyba 122 iteracje. W końcu nie ma co skakać po kolejnych liczbach, skoro wielokrotności 2 na 100% nie pasują i można zacząć od 3, bo test podzielności przez 2 był wcześniej. |
|
michal11 |
» 2016-12-06 11:09:12 Dodam jeszcze, że jeżeli już tak bardzo chcemy żyłować wydajność to zamiast i < std::sqrt( n ) szybsze będzie i * i < n . |
|
« 1 » |