👤
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 pentru vizita pe site-ul nostru dedicat Informatică. Sperăm că informațiile prezentate v-au fost utile. Dacă aveți întrebări sau aveți nevoie de suport suplimentar, nu ezitați să ne contactați. Ne bucurăm să vă revedem și vă invităm să ne adăugați în lista de favorite!


Ze Schools: Alte intrebari