problema biprime #2608 pbinfo
Cerința
Se dă n un număr natural care este produsul a două numere prime distincte, şi m reprezentând numărul numerelor mai mici sau egale cu n, prime cu n. Aflaţi cele două numere prime din descompunerea lui n.
Date de intrare
Programul citește de la tastatură numerele n şi m.
Date de ieșire
Programul va afișa pe ecran numerele prime din descompunerea lui n, în ordine crescătoare, separate prin spaţiu.
Restricții și precizări
1 ≤ m ≤ n ≤ 1025
Exemplu
Intrare
8777 8580
Ieșire
67 131
Explicație
Avem 8777=67•131
https://pastebin.com/SGaEKPMR
Răspunsuri la întrebare
Răspuns:
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
#define lgmax 30
typedef string NrMare;
void citire(NrMare &x){
cin >> x;
}
void scadere(NrMare &a, NrMare b){
int carry = 0;
int i;
while(b.length() < a.length())
b = '0'+b;
for(i = a.length()-1; i >= 0; i--){
a[i] = a[i] - carry - b[i];
if(a[i] < 0){
a[i] += 10;
carry = 1;
} else carry = 0;
a[i] += '0';
}
}
void scadere(NrMare &a, unsigned long long int b){
int carry = 0;
int i;
for(i = a.length()-1; i >= 0; i--){
a[i] = a[i] - '0' - carry - b%10;
b/=10;
if(a[i] < 0){
a[i] += 10;
carry = 1;
} else carry = 0;
a[i] += '0';
}
}
void adunare(NrMare &a, int b){
int carry = 0,i;
for(i = a.length()-1; i >= 0; i--){
a[i] = a[i]-'0' + carry + b % 10;
b /= 10;
if(a[i] > 9){
carry = a[i] / 10;
a[i] %= 10;
}else carry = 0;
a[i] += '0';
}
}
void adunare(NrMare &a, NrMare b){
int carry = 0, i;
int Max = a.length() > b.length() ? a.length() : b.length();
while(a.length() < Max)
a = '0' + a;
while(b.length() < Max)
b = '0' + b;
for(i = Max-1; i >= 0; i--){
a[i] = a[i]- '0' + b[i] - '0' + carry;
if(a[i] > 9){
carry = a[i] / 10;
a[i] %= 10;
}else carry = 0;
a[i] += '0';
}
if(carry)
a[i] = carry;
}
void afisare(NrMare a){
int i;
for(i = 0; a[i] == '0'; i++);
for(; i < a.length(); i++)
cout << a[i];
}
void copie(NrMare &y, NrMare x){
y = x;
}
void citire_str(NrMare &x, string s){
x = s;
}
void sqrt(NrMare &x){
double n = stod(x);
double xk = 1;
for(int i = 0; i < 10000; ++i) {
xk = ( xk + n / xk ) / 2;
}
citire_str(x, to_string((unsigned long long)round(xk)));
}
string longDivision(string number, int divisor)
{
string ans;
int idx = 0;
int temp = number[idx] - '0';
while (temp < divisor)
temp = temp * 10 + (number[++idx] - '0');
while (number.size() > idx)
{
ans += (temp / divisor) + '0';
temp = (temp % divisor) * 10 + number[++idx] - '0';
}
if (ans.length() == 0)
return "0";
return ans;
}
string multiply(string num1, string num2)
{
int n1 = num1.size();
int n2 = num2.size();
if (n1 == 0 || n2 == 0)
return "0";
vector<int> result(n1 + n2, 0);
int i_n1 = 0;
int i_n2 = 0;
for (int i=n1-1; i>=0; i--)
{
int carry = 0;
int n1 = num1[i] - '0';
i_n2 = 0;
for (int j=n2-1; j>=0; j--)
{
int n2 = num2[j] - '0';
int sum = n1*n2 + result[i_n1 + i_n2] + carry;
carry = sum/10;
result[i_n1 + i_n2] = sum % 10;
i_n2++;
}
if (carry > 0)
result[i_n1 + i_n2] += carry;
i_n1++;
}
int i = result.size() - 1;
while (i>=0 && result[i] == 0)
i--;
if (i == -1)
return "0";
string s = "";
while (i >= 0)
s += std::to_string(result[i--]);
return s;
}
NrMare n(lgmax, '0'),m(lgmax, '0'),proc(lgmax, '0'),cache(lgmax, '0'),nori4(lgmax, '0'),a(lgmax, '0');
int main(){
citire(n);
citire(m);
copie(proc, n);// proc = n
scadere(proc, m);// proc = n - m
adunare(proc, 1);// proc = n - m + 1 = c
copie(cache, proc);// cache = c
cache = multiply(cache, cache);// cache = c^2
copie(nori4, n);// nori4 = n
nori4 = multiply(nori4, "4");// nori4 = 4n
scadere(cache, nori4);// cache = c^2 - 4n
sqrt(cache);// cache = sqrt(c^2 - 4n)
copie(a,proc);// a = c
scadere(a, cache);// a = c - sqrt(c^2 - 4n)
cout << longDivision(a,2) << ' ';// afisam ( c-sqrt(c^2-4n) ) / 2 (a-ul)
copie(a,proc);// a = c
adunare(a,cache);// a = c + sqrt(c^2 - 4n)
cout << longDivision(a,2) << '\n'; // afisam ( c + sqrt(c^2 - 4n) )/ 2 (b-ul)
}
Explicație:
Se folosesc numere mari.