imagine-fundal

Blog / Indicatorul lui Euler C++, Python, Java
facebook instagram whatsapp tiktok twitter

     În tutorialul de astăzi vom parcurge algoritmul indicatorul lui Euler. Acesta apare în problemele de performanță și olimpiadă, încât este unul mult mai complex, decât nivelul de clasă, și cere cazuri particulare pentru a fi aplicat. Totodată, poate fi scris în toate limbajele de programare, ca urmare vom parcurge reprezentările în C++ Imagine C++, Python Imagine Python și Java Imagine Java. Acest algoritm ne va inscrie într-un vector soluție, pentru toatele numerele prime cu ținta și mai mici decât aceasta, numărul de numere mai mici și prime cu fiecare element. Mai exact, pentru intrarea 8, vom primi rezultatul 1, 1, 2, 2, 4, 2, 6, 4. Convențional se notează folosind litera grecească Phi Φ, de unde și numele funcției din tutorial. Înainte de a începe să scriem codul vom înteleg cum funcționează. Tehnicile folosite sunt aproximativ aceleași, așa că explicațiile sunt la modul general.

     Citim într-o variabilă numărul introdus de la tastatură. Acum, în funcția phi(), având doi parametrii de intrare, primul reprezentând vectorul soluție, iar cel de-al doilea, numărul țintă (maxim), folosind formula matematică Φ(x) = x * (p1 - 1) * (p2 - 1) * ... * (pk - 1) / (p1 * p2 * ... * pk), unde variabilele p1, p2, ..., pk sunt factorii primi ai numărului x, vom trece în vectorul primit ca parametru, pentru fiecare număr, totalul de numere prime cu acesta și mai mici. După ce toate numerele până la ținta trimisă au primit și afișat rezultatul vom opri funcția.

     Mai jos puteți vedea implementările în limbajele C++, Python și Java și câteva probleme pe care le recomandăm pentru a înțelege mai bine tutorialul de astăzi.

     Probleme recomandate de pe platforma PBinfo: Tramvaie, Eratostene3, maxprimeintrele

Implementarea C++ Imagine C++:

#include <iostream>
using namespace std;
int euler[1000001], n;
int phi(int euler[], int n) {
    for (int i = 1; i <= n; i++)
        euler[i] = i;
    for (int i = 2; i <= n; i++)
        if (euler[i] == i)
            for (int j = i; j <= n; j = j + i)
                euler[j] = euler[j] * (i - 1) / i;
    for (int i = 1; i <= n; i++)
        cout << euler[i] << "
";
    return 0;
}
int main() {
    cin >> n;
    phi(euler, n);
    return 0;
}

Implementarea Python Imagine Python:

def phi(euler, n):
    for i in range(1, n + 1, 1):
        euler[i] = i
    for i in range (2, n + 1, 1):
        if (euler[i] == i):
            for j in range(i, n + 1, i):
                euler[j] = euler[j] * (i - 1) / i;
    for i in range(1, n + 1, 1):
        print(int(euler[i]))
                
euler = [0 for i in range(1, 1000001, 1)]
n = int(input())
phi(euler, n)

Implementarea Java Imagine Java:

import java.util.Scanner;
class Tutorial {
    public static int[] euler = new int[1000001];
    public static int phi(int euler[], int n) {
        for (int i = 1; i <= n; i++)
            euler[i] = i;
        for (int i = 2; i <= n; i++) 
            if (euler[i] == i)
                for (int j = i; j <= n; j = j + i)
                    euler[j] = euler[j] * (i - 1) / i;
        for (int i = 1; i <= n; i++)
            System.out.println(euler[i]);
        return 0;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        phi(euler, n);
    }
}

imagine

pbinfo / 2729

imagine

cssbattle / 6

imagine

pbinfo / 3211