Cerința

Se dă un şir format din n numere naturale, a₁, a₂, …, a_n. O pereche ( a_i, a_j), unde i<j, se numeşte eratostenică dacă i divide pe j şi a_i divide pe a_j. Determinaţi câte perechi eratostenice conţine şirul dat.

Date de intrare

Fișierul de intrare eratostene6.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire eratostene6.out va conține pe prima linie numărul perechilor eratostenice din şirul dat.

Restricții și precizări

2 ≤ n ≤ 100.000
0 ≤ a₁, a₂, …, a_n ≤ 1.000

Exemplu

eratostene6.in

4
2 3 0 6

eratostene6.out

Explicație

Cele 3 perechi eratostenice sunt: (2,0), (2,6), (3,6).

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Eratostene6:

#include <fstream>
#define N 100000
using namespace std;
ifstream fi("eratostene6.in");
ofstream fo("eratostene6.out");
int i, n, j, k, m;
int a[N+1];

int main()
{
    fi >> n;
    for(i = 1; i <= n; i++)
        fi >> a[i];
    m = n / 2;
    k = 0;
    for(i = 1; i <= m; i++)
    {
        j = i + i;
        while(j <= n)
        {
            if(a[i] != 0)
            {
                if(a[j] % a[i] == 0) k++;
            }
            else
                if(a[j]==0) k++;
            j = j + i;
        }
    }
    fo << k;
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #3317 Eratostene6

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3317 Eratostene6 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #3317 Eratostene6