Pomoc oko zadatka (Cubes)

Pitanja i problemi
1

Pitanje ili opis problema

Postovani. Pokusao sam da resim ovaj zadatak, ali moj program dobije status TLE na dva test primera. Da li bi neko podelio ideju kako da poboljsam resenje? Hvala unapred.

Link ka zadatku ili odgovarajućoj stranici

https://petlja.org/biblioteka/r/Problemi/2009-kvalifikacije-I-ss-cubes

Moj kod

#include <bits/stdc++.h>
#define ll long long

using namespace std;

bool prost(ll n) {
     if(n < 2) return false;
     for(int x = 2; x*x <= n; x++) {
         if(n % x == 0) return false;
     }
     return true;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int n;

  cin >> n;
  while(n--) {
      ll k;
      cin >> k;

      if(prost(k) || k < 4) cout << "NE" << endl;
      else cout << "DA" << endl;
  }

  return 0;
}
1 Like
2

Cao, potrebno je da ubrzas funkciju koja proverava da li je broj prost tako sto ces da iskoristis cinjenicu da svi brojevi veci od 2 moraju biti neparni pa bi ova petlja u tvojoj funkciju bila for(x=3; x*x<=n;x+=2) s tim sto ti na pocetku funkcije treba uslov da li je n jednako 2

1 Like
4

Cao. Hvala na odgovoru, ali dobijam TLE na ista dva test primera kada je ubrzam tako.

5

Mozes da uradis zadatak preko faktorizacije, ja sam ga tako uradio (Proveris koliko razlicitih prostih faktora ima broj)

1 Like