Re9 - A1

PROBLEME RECAPITULATIVE – clasa a 9-a
ANEXA 1 : Un număr este palindrom-ciclic dacă devine un palindrom printr-un număr de permutări circulare. Să se înlocuiască toate valorile palindrom-ciclic din triunghiul de nord cu suma elementelor aproape prime din triunghiul de est. Un număr este aproape prim dacă se scrie ca produs de două numere prime distincte.

	#include <iostream>
        using namespace std;

        #define lim 501
        #define bound 50000

		void citire(int &n, long long a[][lim]){
            cin >> n;
            for(int i=1; i<=n; i++)
                for(int j=1; j<=n; j++)
                    cin >> a[i][j];
        }

        int prime[6000];
        bool compus[bound+1];

        void cautaPrime(){
            compus[0] = compus[1] = true;

            for(int i=4; i<=bound; i+=2)
                compus[i] = true;

            for(int i=3; i*i<=bound; i+=2)
                if(!compus[i])
                    for(int j=i*i; j<=bound; j+=2*i)
                        compus[j] = true;
            int k = 0;
            prime[++k] = 2;
            for(int i=3; i<=bound; i+=2)
                if(!compus[i])
                    prime[++k] = i;
        }

        bool isPrime(int num){
            if(num <= 1)
                return false;

            for(int i=1; prime[i] * prime[i] <= num; i++)
                if(num % prime[i] == 0)
                    return false;
            return true;
        }

        bool esteAproapePrim(int num){

            for(int i=1; i*i < num; i++)
                if(num != 2 * i && isPrime(i) && isPrime(num/i))
                    return true;
            return false;
        }

        void cautaAP(int n, long long a[][lim], long long &sumAP, int &ct){
            for(int j=(n+1)/2 + 1; j<=n; j++)
                for(int i = n - j + 2; i <= j - 1; i++)
                    if(esteAproapePrim(a[i][j]))
                        sumAP += a[i][j], ct++;
        }

        long long oglindit(int num){
            long long og = 0;
            do{
                int digit = num % 10;
                num /= 10;
                og = 1ll * (og * 10 + digit);
            }while(num);
            return og;
        }

        int log10(int num){
            int f = 1;
            while(num > 9){
                f *= 10;
                num /= 10;
            }
            return f;
        }

        long long perm(long long num, int f){
            return num % 10 * f + num / 10;
        }

        bool estePalCyc(int num){

            long long aux = num;
            int f = log10(num);
            do{
                if(1ll * num == oglindit(num))
                    return true;
                num = perm(num, f);
            }while(1ll * num != aux);
            return false;
        }

        void modifTablou(int n, long long a[][lim], long long sumAP, int &ct){
            for(int i=1; i<=(n+1)/2; i++)
                for(int j=i+1; j<=n-i; j++)
                    if(estePalCyc(a[i][j]))
                        a[i][j] = sumAP, ct++;

        }

        void display(int n, long long a[][lim], long long sumAP, int ct1, int ct2){
            cout << "S-au realizat " << ct2 << " modificari, dependente de suma" << sumAP << ", compusa pe baza a " << ct1 << " numere.\n";
            cout << "Iata tabloul trecut prin proces  : \n";
            for(int i=1; i<=n; i++){
                for(int j=1; j<=n; j++)
                    cout << a[i][j] << " ";
                cout << "\n";
            }
        }
        int main()
        {
            int n;
            long long a[lim][lim];
            citire(n, a);

            cautaPrime();

            long long sumAP = 0;
            int ct1 = 0;
            cautaAP(n, a, sumAP, ct1);

            int ct2 = 0;
            modifTablou(n, a, sumAP, ct2);

            display(n, a, sumAP, ct1, ct2);
            return 0;
        }