Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Błędy w programie znajdowania liczb pierwszych

Ostatnio zmodyfikowano 2016-12-06 11:09
Autor Wiadomość
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;
}
}
}
P-154436
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.

C/C++
#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;
}
P-154563
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.
P-154568
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
P-154570
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.
P-154571
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
.
P-154577
« 1 »
  Strona 1 z 1