RO Learnings
a fost răspuns

#3460 FirstPrime - pbinfo
Cerința
Se dau n numere naturale. Definim FP(x) cel mai mic număr prim care îl divide pe x. Aflați suma FP-urilor celor n numere.
Date de intrare
Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații.
Date de ieșire
Programul va afișa pe ecran numărul S.
Restricții și precizări
2 ≤ n ≤ 1.000.000
cele n numere citite vor fi mai mici decât 100.000.000

Răspuns :

Răspuns:

#include <bits/stdc++.h>

namespace FastRead {

   const int Dim(5000);

   char ibuf[Dim];

   int ipos, ilen;

   char nc()

   {

       if (ipos == ilen)

       {

           ipos = 0;

           ilen = fread(ibuf, 1, Dim, stdin);

           if (!ilen) return EOF;

       }

       return ibuf[ipos++];

   }

   template<class T> void read(T& x)

   {

       char ch;

       int sgn = 1;

       while (!isdigit(ch = nc()))

           if (ch == '-')

               sgn = -1;

       x = ch - '0';

       while (isdigit(ch = nc()))

           x = x * 10 + (ch - '0');

       x *= sgn;

   }

}

using namespace FastRead;

using namespace std;

const int N(1e8);

int lp[N + 1];

vector<int> pr;

int n, x, to;

int64_t res;

int main()

{

   for (int i = 3; i <= N; i += 2) {

       if (lp[i] == 0) {

           lp[i] = i;

           pr.emplace_back(i);

       }

       to = min(N / i, lp[i]);

       for (int j = 0; j < static_cast<int>(pr.size()) && pr[j] <= to; ++j)

           lp[i * pr[j]] = pr[j];

   }

   read(n);

   for (int i = 1; i <= n; ++i) {

       read(x);

       if (x % 2 == 0 && x > 1)

           res += 2;

       else res += lp[x];

   }

   cout << res;

   return 0;

}

Explicație:

Vă mulțumim că ați ales să vizitați platforma noastră dedicată Informatică. Sperăm că ați găsit conținutul oferit util și inspirațional. Dacă aveți întrebări suplimentare sau doriți asistență, vă încurajăm să ne contactați. Ne-ar face plăcere să reveniți și nu uitați să ne adăugați în lista dumneavoastră de favorite!


RO Learnings: Alte intrebari